livefiles_hfs_plugin/lf_hfs_btree_misc_ops.c

   1 //
   2 //  lf_hfs_btree_misc_ops.c
   3 //  livefiles_hfs
   4 //
   5 //  Created by Yakov Ben Zaken on 22/03/2018.
   6 //
   7
   8 #include "lf_hfs_btrees_private.h"
   9 #include "lf_hfs_btrees_io.h"
  10 #include "lf_hfs_utils.h"
  11
  12 ////////////////////////////// Routine Definitions //////////////////////////////
  13
  14 /*-------------------------------------------------------------------------------
  15  Routine:    CalcKeyRecordSize    -    Return size of combined key/record structure.
  16
  17  Function:    Rounds keySize and recSize so they will end on word boundaries.
  18  Does NOT add size of offset.
  19
  20  Input:        keySize        - length of key (including length field)
  21  recSize        - length of record data
  22
  23  Output:        none
  24
  25  Result:        u_int16_t    - size of combined key/record that will be inserted in btree
  26  -------------------------------------------------------------------------------*/
  27
  28 u_int16_t        CalcKeyRecordSize        (u_int16_t                 keySize,
  29                                            u_int16_t                 recSize )
  30 {
  31     if ( M_IsOdd (keySize) )    keySize += 1;    // pad byte
  32
  33     if (M_IsOdd (recSize) )        recSize += 1;    // pad byte
  34
  35     return    (keySize + recSize);
  36 }
  37
  38
  39
  40 /*-------------------------------------------------------------------------------
  41  Routine:    VerifyHeader    -    Validate fields of the BTree header record.
  42
  43  Function:    Examines the fields of the BTree header record to determine if the
  44  fork appears to contain a valid BTree.
  45
  46  Input:        forkPtr        - pointer to fork control block
  47  header        - pointer to BTree header
  48
  49
  50  Result:        noErr        - success
  51  != noErr    - failure
  52  -------------------------------------------------------------------------------*/
  53
  54 OSStatus    VerifyHeader    (FCB                *filePtr,
  55                              BTHeaderRec             *header )
  56 {
  57     u_int64_t        forkSize;
  58     u_int32_t        totalNodes;
  59
  60
  61     switch (header->nodeSize)                            // node size == 512*2^n
  62     {
  63         case   512:
  64         case  1024:
  65         case  2048:
  66         case  4096:
  67         case  8192:
  68         case 16384:
  69         case 32768:        break;
  70         default:        return    fsBTInvalidHeaderErr;            //E_BadNodeType
  71     }
  72
  73     totalNodes = header->totalNodes;
  74
  75     forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize;
  76
  77     if ( forkSize > (u_int64_t)filePtr->fcbEOF )
  78         return fsBTInvalidHeaderErr;
  79
  80     if ( header->freeNodes >= totalNodes )
  81         return fsBTInvalidHeaderErr;
  82
  83     if ( header->rootNode >= totalNodes )
  84         return fsBTInvalidHeaderErr;
  85
  86     if ( header->firstLeafNode >= totalNodes )
  87         return fsBTInvalidHeaderErr;
  88
  89     if ( header->lastLeafNode >= totalNodes )
  90         return fsBTInvalidHeaderErr;
  91
  92     if ( header->treeDepth > kMaxTreeDepth )
  93         return fsBTInvalidHeaderErr;
  94
  95
  96     /////////////////////////// Check BTree Type ////////////////////////////////
  97
  98     switch (header->btreeType)
  99     {
 100         case    0:                    // HFS Type - no Key Descriptor
 101         case    kUserBTreeType:        // with Key Descriptors etc.
 102         case    kReservedBTreeType:    // Desktop Mgr BTree ?
 103             break;
 104
 105         default:                    return fsBTUnknownVersionErr;
 106     }
 107
 108     return noErr;
 109 }
 110
 111
 112
 113 OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr)
 114 {
 115     return (btreePtr->flags & kBTHeaderDirty);
 116 }
 117
 118
 119
 120 /*-------------------------------------------------------------------------------
 121  Routine:    UpdateHeader    -    Write BTreeInfoRec fields to Header node.
 122
 123  Function:    Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
 124  header node if necessary.
 125
 126  Input:        btreePtr        - pointer to BTreeInfoRec
 127
 128
 129  Result:        noErr        - success
 130  != noErr    - failure
 131  -------------------------------------------------------------------------------*/
 132
 133 OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite)
 134 {
 135     OSStatus                err;
 136     BlockDescriptor            node;
 137     BTHeaderRec    *header;
 138     u_int32_t options;
 139
 140     if ((btreePtr->flags & kBTHeaderDirty) == 0)            // btree info already flushed
 141         return    noErr;
 142
 143     err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
 144     if (err != noErr) {
 145         return    err;
 146     }
 147
 148     // XXXdbg
 149     ModifyBlockStart(btreePtr->fileRefNum, &node);
 150
 151     header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor));
 152
 153     header->treeDepth        = btreePtr->treeDepth;
 154     header->rootNode        = btreePtr->rootNode;
 155     header->leafRecords        = btreePtr->leafRecords;
 156     header->firstLeafNode    = btreePtr->firstLeafNode;
 157     header->lastLeafNode    = btreePtr->lastLeafNode;
 158     header->nodeSize        = btreePtr->nodeSize;            // this shouldn't change
 159     header->maxKeyLength    = btreePtr->maxKeyLength;        // neither should this
 160     header->totalNodes        = btreePtr->totalNodes;
 161     header->freeNodes        = btreePtr->freeNodes;
 162     header->btreeType        = btreePtr->btreeType;
 163
 164     // ignore    header->clumpSize;                            // rename this field?
 165
 166     if (forceWrite)
 167         options = kForceWriteBlock;
 168     else
 169         options = kLockTransaction;
 170
 171     err = UpdateNode (btreePtr, &node, 0, options);
 172
 173     btreePtr->flags &= (~kBTHeaderDirty);
 174
 175     return    err;
 176 }
 177
 178
 179
 180 /*-------------------------------------------------------------------------------
 181  Routine:    FindIteratorPosition    -    One_line_description.
 182
 183  Function:    Brief_description_of_the_function_and_any_side_effects
 184
 185  Algorithm:    see FSC.BT.BTIterateRecord.PICT
 186
 187  Note:        // document side-effects of bad node hints
 188
 189  Input:        btreePtr        - description
 190  iterator        - description
 191
 192
 193  Output:        iterator        - description
 194  left            - description
 195  middle            - description
 196  right            - description
 197  nodeNum            - description
 198  returnIndex        - description
 199  foundRecord        - description
 200
 201
 202  Result:        noErr        - success
 203  != noErr    - failure
 204  -------------------------------------------------------------------------------*/
 205
 206 OSStatus    FindIteratorPosition    (BTreeControlBlockPtr     btreePtr,
 207                                      BTreeIteratorPtr         iterator,
 208                                      BlockDescriptor        *left,
 209                                      BlockDescriptor        *middle,
 210                                      BlockDescriptor        *right,
 211                                      u_int32_t                *returnNodeNum,
 212                                      u_int16_t                *returnIndex,
 213                                      Boolean                *foundRecord )
 214 {
 215     OSStatus        err;
 216     Boolean            foundIt;
 217     u_int32_t        nodeNum;
 218     u_int16_t        leftIndex,    index,    rightIndex;
 219     Boolean            validHint;
 220
 221     // assume btreePtr valid
 222     // assume left, middle, right point to BlockDescriptors
 223     // assume nodeNum points to u_int32_t
 224     // assume index points to u_int16_t
 225     // assume foundRecord points to Boolean
 226
 227     left->buffer        = nil;
 228     left->blockHeader   = nil;
 229     middle->buffer        = nil;
 230     middle->blockHeader    = nil;
 231     right->buffer        = nil;
 232     right->blockHeader    = nil;
 233
 234     foundIt                = false;
 235
 236     if (iterator == nil)                        // do we have an iterator?
 237     {
 238         err = fsBTInvalidIteratorErr;
 239         goto ErrorExit;
 240     }
 241
 242     err = IsItAHint (btreePtr, iterator, &validHint);
 243     M_ExitOnError (err);
 244
 245     nodeNum = iterator->hint.nodeNum;
 246     if (! validHint)                            // does the hint appear to be valid?
 247     {
 248         goto SearchTheTree;
 249     }
 250
 251     err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
 252     if( err == fsBTInvalidNodeErr )    // returned if nodeNum is out of range
 253         goto SearchTheTree;
 254
 255     M_ExitOnError (err);
 256
 257     if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
 258         ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
 259     {
 260         goto SearchTheTree;
 261     }
 262
 263     foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
 264     if (foundIt == true)
 265     {
 266         ++btreePtr->numValidHints;
 267         goto SuccessfulExit;
 268     }
 269     iterator->hint.nodeNum = 0;
 270
 271     if (index == 0)
 272     {
 273         if (((NodeDescPtr) middle->buffer)->bLink == 0)        // before 1st btree record
 274         {
 275             goto SuccessfulExit;
 276         }
 277
 278         nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
 279
 280         // BTree nodes are always grabbed in left to right order.
 281         // Therefore release the current node before looking up the
 282         // left node.
 283         err = ReleaseNode(btreePtr, middle);
 284         M_ExitOnError(err);
 285
 286         // Look up the left node
 287         err = GetNode (btreePtr, nodeNum, 0, left);
 288         M_ExitOnError (err);
 289
 290         // Look up the current node again
 291         err = GetRightSiblingNode (btreePtr, left->buffer, middle);
 292         M_ExitOnError (err);
 293
 294         if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
 295             ((NodeDescPtr) left->buffer)->numRecords <= 0 )
 296         {
 297             goto SearchTheTree;
 298         }
 299
 300         foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
 301         if (foundIt == true)
 302         {
 303             *right            = *middle;
 304             *middle            = *left;
 305             left->buffer    = nil;
 306             index            = leftIndex;
 307
 308             goto SuccessfulExit;
 309         }
 310
 311         if (leftIndex == 0)                                    // we're lost!
 312         {
 313             goto SearchTheTree;
 314         }
 315         else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
 316         {
 317             nodeNum = ((NodeDescPtr) left->buffer)->fLink;
 318             if (index != 0)
 319             {
 320                 LFHFS_LOG(LEVEL_ERROR, "FindIteratorPosition: index != 0\n");
 321                 hfs_assert(0);
 322             }
 323             goto SuccessfulExit;
 324         }
 325         else
 326         {
 327             *right            = *middle;
 328             *middle            = *left;
 329             left->buffer    = nil;
 330             index            = leftIndex;
 331
 332             goto SuccessfulExit;
 333         }
 334     }
 335     else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
 336     {
 337         if (((NodeDescPtr) middle->buffer)->fLink == 0)    // beyond last record
 338         {
 339             goto SuccessfulExit;
 340         }
 341
 342         nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
 343
 344         err = GetRightSiblingNode (btreePtr, middle->buffer, right);
 345         M_ExitOnError (err);
 346
 347         if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
 348             ((NodeDescPtr) right->buffer)->numRecords <= 0 )
 349         {
 350             goto SearchTheTree;
 351         }
 352
 353         foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
 354         if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords)        // we're lost
 355         {
 356             goto SearchTheTree;
 357         }
 358         else    // we found it, or rightIndex==0, or rightIndex<numRecs
 359         {
 360             *left            = *middle;
 361             *middle            = *right;
 362             right->buffer    = nil;
 363             index            = rightIndex;
 364
 365             goto SuccessfulExit;
 366         }
 367     }
 368
 369
 370     //////////////////////////// Search The Tree ////////////////////////////////
 371
 372 SearchTheTree:
 373     {
 374         TreePathTable    treePathTable;        // so we only use stack space if we need to
 375
 376         err = ReleaseNode (btreePtr, left);            M_ExitOnError (err);
 377         err = ReleaseNode (btreePtr, middle);        M_ExitOnError (err);
 378         err = ReleaseNode (btreePtr, right);        M_ExitOnError (err);
 379
 380         err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
 381         switch (err)                // separate find condition from exceptions
 382         {
 383             case noErr:            foundIt = true;                break;
 384             case fsBTRecordNotFoundErr:                        break;
 385             default:                goto ErrorExit;
 386         }
 387     }
 388
 389     /////////////////////////////// Success! ////////////////////////////////////
 390
 391 SuccessfulExit:
 392
 393     *returnNodeNum    = nodeNum;
 394     *returnIndex     = index;
 395     *foundRecord    = foundIt;
 396
 397     return    noErr;
 398
 399
 400     ////////////////////////////// Error Exit ///////////////////////////////////
 401
 402 ErrorExit:
 403
 404     (void)    ReleaseNode (btreePtr, left);
 405     (void)    ReleaseNode (btreePtr, middle);
 406     (void)    ReleaseNode (btreePtr, right);
 407
 408     *returnNodeNum    = 0;
 409     *returnIndex     = 0;
 410     *foundRecord    = false;
 411
 412     return    err;
 413 }
 414
 415
 416
 417 /////////////////////////////// CheckInsertParams ///////////////////////////////
 418
 419 OSStatus    CheckInsertParams        (FCB                        *filePtr,
 420                                       BTreeIterator                *iterator,
 421                                       FSBufferDescriptor            *record,
 422                                       u_int16_t                     recordLen )
 423 {
 424     BTreeControlBlockPtr    btreePtr;
 425
 426     if (filePtr == nil)                                    return    paramErr;
 427
 428     btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 429     if (btreePtr == nil)                                return    fsBTInvalidFileErr;
 430     if (iterator == nil)                                return    paramErr;
 431     if (record     == nil)                                return    paramErr;
 432
 433     //    check total key/record size limit
 434     if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
 435         return    fsBTRecordTooLargeErr;
 436
 437     return    noErr;
 438 }
 439
 440
 441
 442 /*-------------------------------------------------------------------------------
 443  Routine:    TrySimpleReplace    -    Attempts a simple insert, set, or replace.
 444
 445  Function:    If a hint exitst for the iterator, attempt to find the key in the hint
 446  node. If the key is found, an insert operation fails. If the is not
 447  found, a replace operation fails. If the key was not found, and the
 448  insert position is greater than 0 and less than numRecords, the record
 449  is inserted, provided there is enough freeSpace.  If the key was found,
 450  and there is more freeSpace than the difference between the new record
 451  and the old record, the old record is deleted and the new record is
 452  inserted.
 453
 454  Assumptions:    iterator key has already been checked by CheckKey
 455
 456
 457  Input:        btreePtr        - description
 458  iterator        - description
 459  record            - description
 460  recordLen        - description
 461  operation        - description
 462
 463
 464  Output:        recordInserted        - description
 465
 466
 467  Result:        noErr            - success
 468  E_RecordExits        - insert operation failure
 469  != noErr        - GetNode, ReleaseNode, UpdateNode returned an error
 470  -------------------------------------------------------------------------------*/
 471
 472 OSStatus    TrySimpleReplace        (BTreeControlBlockPtr     btreePtr,
 473                                      NodeDescPtr             nodePtr,
 474                                      BTreeIterator            *iterator,
 475                                      FSBufferDescriptor        *record,
 476                                      u_int16_t                 recordLen,
 477                                      Boolean                *recordInserted )
 478 {
 479     u_int32_t            oldSpace;
 480     u_int32_t            spaceNeeded;
 481     u_int16_t            index;
 482     u_int16_t            keySize;
 483     Boolean                foundIt;
 484     Boolean                didItFit;
 485
 486
 487     *recordInserted    = false;                                // we'll assume this won't work...
 488
 489     if ( nodePtr->kind != kBTLeafNode )
 490         return    noErr;    // we're in the weeds!
 491
 492     foundIt    = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
 493
 494     if ( foundIt == false )
 495         return    noErr;    // we might be lost...
 496
 497     keySize = CalcKeySize(btreePtr, &iterator->key);    // includes length field
 498
 499     spaceNeeded    = CalcKeyRecordSize (keySize, recordLen);
 500
 501     oldSpace = GetRecordSize (btreePtr, nodePtr, index);
 502
 503     if ( spaceNeeded == oldSpace )
 504     {
 505         u_int8_t *        dst;
 506
 507         dst = GetRecordAddress (btreePtr, nodePtr, index);
 508
 509         if ( M_IsOdd (keySize) )
 510             ++keySize;            // add pad byte
 511
 512         dst += keySize;        // skip over key to point at record
 513
 514         BlockMoveData(record->bufferAddress, dst, recordLen);    // blast away...
 515
 516         *recordInserted = true;
 517     }
 518     else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
 519     {
 520         DeleteRecord (btreePtr, nodePtr, index);
 521
 522         didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
 523                                     &iterator->key, KeyLength(btreePtr, &iterator->key),
 524                                     record->bufferAddress, recordLen);
 525         if (didItFit == false)
 526         {
 527             LFHFS_LOG(LEVEL_ERROR, "TrySimpleInsert: InsertKeyRecord returned false!");
 528             hfs_assert(0);
 529         }
 530         *recordInserted = true;
 531     }
 532     // else not enough space...
 533
 534     return    noErr;
 535 }
 536
 537
 538 /*-------------------------------------------------------------------------------
 539  Routine:    IsItAHint    -    checks the hint within a BTreeInterator.
 540
 541  Function:    checks the hint within a BTreeInterator.  If it is non-zero, it may
 542  possibly be valid.
 543
 544  Input:        btreePtr    - pointer to control block for BTree file
 545  iterator    - pointer to BTreeIterator
 546
 547  Output:        answer        - true if the hint looks reasonable
 548  - false if the hint is 0
 549
 550  Result:        noErr            - success
 551  -------------------------------------------------------------------------------*/
 552
 553
 554 OSStatus    IsItAHint    (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
 555 {
 556     ++btreePtr->numHintChecks;
 557     if (iterator->hint.nodeNum == 0)
 558     {
 559         *answer = false;
 560     }
 561     else
 562     {
 563         *answer = true;
 564         ++btreePtr->numPossibleHints;
 565     }
 566
 567     return noErr;
 568 }