core/BTreesPrivate.h

   1 /*
   2  * Copyright (c) 2000-2015 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_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. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /*
  29         File:           BTreesPrivate.h
  30
  31         Contains:       Private interface file for the BTree Module.
  32
  33         Version:        xxx put the technology version here xxx
  34
  35         Written by:     Gordon Sheridan and Bill Bruffey
  36
  37         Copyright:      (c) 1992-1999 by Apple Inc., all rights reserved.
  38
  39         File Ownership:
  40
  41                 DRI:                            Don Brady
  42
  43                 Other Contact:          Mark Day
  44
  45                 Technology:                     File Systems
  46
  47         Writers:
  48
  49                 (msd)   Mark Day
  50                 (DSH)   Deric Horn
  51                 (djb)   Don Brady
  52                 (ser)   Scott Roberts
  53                 (dkh)   Dave Heller
  54
  55         Change History (most recent first):
  56            <MacOSX>      3/19/99        djb             Disable MoveRecordsLeft/Right macros since bcopy is broken.
  57
  58            <MacOSX>      8/10/98        djb             Removed unused BTreeIterator from BTreeControlBlock, fixed alignment.
  59
  60            <CS5>          9/4/97        djb             Convert MoveRecordsLeft and GetLeftSiblingNode to macros.
  61            <CS4>         7/24/97        djb             Add macro for GetRecordAddress (was a function before).
  62            <CS3>         7/21/97        msd             GetRecordByIndex now returns an OSStatus.
  63            <CS2>         7/16/97        DSH             FilesInternal.i renamed FileMgrInternal.i to avoid name
  64                                                                         collision
  65            <CS1>         4/23/97        djb             first checked in
  66
  67           <HFS6>         3/17/97        DSH             Added a refCon field to BTreeControlBlock, for DFA use, to point
  68                                                                         to additional data.  Fixed Panic macros for use with SC.
  69           <HFS5>         2/19/97        djb             Add InsertKey struct. Moved on-disk definitions to
  70                                                                         HFSBTreesPriv.h
  71           <HFS4>         1/27/97        djb             InsertTree and DeleteTree are now recursive and support variable
  72                                                                         sized index keys.
  73           <HFS3>         1/15/97        djb             Move GetFileRefNumFromFCB macro to FilesInternal.h. Added
  74                                                                         kBTVariableIndexKeysMask.
  75           <HFS2>          1/3/97        djb             Added support for large keys.
  76           <HFS1>        12/19/96        djb             first checked in
  77
  78         History applicable to original Scarecrow Design:
  79
  80                  <7>    10/25/96        ser             Changing for new VFPI
  81                  <6>    10/18/96        ser             Converting over VFPI changes
  82                  <5>     9/17/96        dkh             More BTree statistics
  83                  <4>     9/16/96        dkh             Revised BTree statistics
  84                  <3>     6/20/96        dkh             Radar #1358740. Switch from using Pools to debug MemAllocators.
  85                  <2>     12/7/95        dkh             D10E2 build. Changed usage of Ref data type to LogicalAddress.
  86                  <1>    10/18/95        rst             Moved from Scarecrow project.
  87
  88                 <19>    11/22/94        djb             Add prototype for GetMapNode
  89                 <18>    11/16/94        prp             Add IsItAHint routine prototype.
  90                 <17>     9/30/94        prp             Get in sync with D2 interface changes.
  91                 <16>     7/25/94        wjk             Eliminate usage of BytePtr in favor of UInt8 *.
  92                 <15>     7/22/94        wjk             Convert to the new set of header files.
  93                 <14>     5/31/94        srs             Moved Btree types to public interface
  94                 <13>     12/9/93        wjk             Add 68k alignment pragma's around persistent structures.
  95                 <12>    11/30/93        wjk             Move from Makefiles to BuildFiles. Fit into the ModernOS and
  96                                                                         NRCmds environments.
  97                 <11>    11/23/93        wjk             Changes required to compile on the RS6000.
  98                 <10>     8/30/93        CH              Removed the M_ExitOnError and M_ReturnErrorIf macros which were
  99                                                                         already defined in FileSystemPriv.h (included here).
 100                  <9>     8/30/93        CH              Added parens around the M_ReturnErrorIf macro.
 101                  <8>     5/21/93        gs              Add kBadClose flag. Add some prototypes for internal routines.
 102                  <7>     5/10/93        gs              Change Ptr to BytePtr. Move BTreeTypes to BTree.h. Add
 103                                                                         DeleteTree prototype.
 104                  <6>     3/23/93        gs              Remove mysterious "flags" field from HeaderRec structure. Move
 105                                                                         prototypes of private functions to top of respective source
 106                                                                         files.
 107                  <5>      2/8/93        gs              Update to use FSAgent.h Get/Release/SetEOF/SetBlockSize
 108                                                                         procPtrs. Add UpdateNode routine.
 109                  <4>    12/10/92        gs              Add Key Descriptor function declarations.
 110                  <3>     12/8/92        gs              Add HeaderRec structure and incorporate review feedback.
 111                  <2>     12/2/92        gs              Add GetNode and ReleaseNode callback procptrs to BTree CB, and
 112                                                                         add internal function declarations.
 113                  <1>    11/15/92        gs              first checked in
 114
 115 */
 116
 117 #ifndef __BTREESPRIVATE__
 118 #define __BTREESPRIVATE__
 119
 120 #include <sys/appleapiopts.h>
 121
 122 #ifdef KERNEL
 123 #ifdef __APPLE_API_PRIVATE
 124
 125 #include "hfs_macos_defs.h"
 126
 127 #ifndef __FILEMGRINTERNAL__
 128 #include "FileMgrInternal.h"
 129 #endif
 130
 131 #ifndef __BTREESINTERNAL__
 132 #include "BTreesInternal.h"
 133 #endif
 134
 135
 136 /////////////////////////////////// Constants ///////////////////////////////////
 137
 138 #define         kBTreeVersion             1
 139 #define         kMaxTreeDepth            16
 140
 141
 142 #define         kHeaderNodeNum            0
 143 #define         kKeyDescRecord            1
 144
 145
 146 // Header Node Record Offsets
 147 enum {
 148         kHeaderRecOffset        =       0x000E,
 149         kKeyDescRecOffset       =       0x0078,
 150         kHeaderMapRecOffset     =       0x00F8
 151 };
 152
 153 #define         kMinNodeSize            512
 154
 155 #define         kMinRecordSize            6
 156                                                                                 // where is minimum record size enforced?
 157
 158 // miscellaneous BTree constants
 159 enum {
 160                         kOffsetSize                             = 2
 161 };
 162
 163 // Insert Operations
 164 typedef enum {
 165                         kInsertRecord                   = 0,
 166                         kReplaceRecord                  = 1
 167 } InsertType;
 168
 169 // illegal string attribute bits set in mask
 170 #define         kBadStrAttribMask               0xCF
 171
 172
 173
 174 //////////////////////////////////// Macros /////////////////////////////////////
 175
 176 #define         M_NodesInMap(mapSize)                           ((mapSize) << 3)
 177
 178 #define         M_ClearBitNum(integer,bitNumber)        ((integer) &= (~(1<<(bitNumber))))
 179 #define         M_SetBitNum(integer,bitNumber)          ((integer) |= (1<<(bitNumber)))
 180 #define         M_IsOdd(integer)                                        (((integer) & 1) != 0)
 181 #define         M_IsEven(integer)                                       (((integer) & 1) == 0)
 182
 183 #define         M_MapRecordSize(nodeSize)                       (nodeSize - sizeof (BTNodeDescriptor) - 6)
 184 #define         M_HeaderMapRecordSize(nodeSize)         (nodeSize - sizeof(BTNodeDescriptor) - sizeof(BTHeaderRec) - 128 - 8)
 185
 186 #define         M_SWAP_BE16_ClearBitNum(integer,bitNumber)  ((integer) &= SWAP_BE16(~(1<<(bitNumber))))
 187 #define         M_SWAP_BE16_SetBitNum(integer,bitNumber)    ((integer) |= SWAP_BE16(1<<(bitNumber)))
 188
 189 ///////////////////////////////////// Types /////////////////////////////////////
 190
 191 typedef struct BTreeControlBlock {                                      // fields specific to BTree CBs
 192
 193         u_int8_t                keyCompareType;   /* Key string Comparison Type */
 194         u_int8_t                                         btreeType;
 195         u_int16_t                                        treeDepth;
 196         FileReference                            fileRefNum;            // refNum of btree file
 197         KeyCompareProcPtr                        keyCompareProc;
 198         u_int32_t                                        rootNode;
 199         u_int32_t                                        leafRecords;
 200         u_int32_t                                        firstLeafNode;
 201         u_int32_t                                        lastLeafNode;
 202         u_int16_t                                        nodeSize;
 203         u_int16_t                                        maxKeyLength;
 204         u_int32_t                                        totalNodes;
 205         u_int32_t                                        freeNodes;
 206
 207         u_int16_t                                        reserved3;                     // 4-byte alignment
 208
 209         // new fields
 210         int16_t                                          version;
 211         u_int32_t                                        flags;                         // dynamic flags
 212         u_int32_t                                        attributes;            // persistent flags
 213         u_int32_t                                        writeCount;
 214         u_int32_t                                        lastfsync;             /* Last time that this was fsynced  */
 215
 216         GetBlockProcPtr                          getBlockProc;
 217         ReleaseBlockProcPtr                      releaseBlockProc;
 218         SetEndOfForkProcPtr                      setEndOfForkProc;
 219
 220         // statistical information
 221         u_int32_t                                        numGetNodes;
 222         u_int32_t                                        numGetNewNodes;
 223         u_int32_t                                        numReleaseNodes;
 224         u_int32_t                                        numUpdateNodes;
 225         u_int32_t                                        numMapNodesRead;       // map nodes beyond header node
 226         u_int32_t                                        numHintChecks;
 227         u_int32_t                                        numPossibleHints;      // Looks like a formated hint
 228         u_int32_t                                        numValidHints;         // Hint used to find correct record.
 229         u_int32_t                                       reservedNodes;
 230         BTreeIterator   iterator; // useable when holding exclusive b-tree lock
 231
 232 #if DEBUG
 233         void                                            *madeDirtyBy[2];
 234 #endif
 235 } BTreeControlBlock, *BTreeControlBlockPtr;
 236
 237 u_int32_t CalcKeySize(const BTreeControlBlock *btcb, const BTreeKey *key);
 238 #define CalcKeySize(btcb, key)                  ( ((btcb)->attributes & kBTBigKeysMask) ? ((key)->length16 + 2) : ((key)->length8 + 1) )
 239
 240 u_int32_t KeyLength(const BTreeControlBlock *btcb, const BTreeKey *key);
 241 #define KeyLength(btcb, key)                    ( ((btcb)->attributes & kBTBigKeysMask) ? (key)->length16 : (key)->length8 )
 242
 243
 244
 245 typedef enum {
 246                                         kBTHeaderDirty  = 0x00000001
 247 }       BTreeFlags;
 248
 249 static inline void M_BTreeHeaderDirty(BTreeControlBlock *bt) {
 250 #if DEBUG
 251         bt->madeDirtyBy[0] = __builtin_return_address(0);
 252         bt->madeDirtyBy[1] = __builtin_return_address(1);
 253 #endif
 254         bt->flags |= kBTHeaderDirty;
 255 }
 256
 257 typedef int8_t                          *NodeBuffer;
 258 typedef BlockDescriptor          NodeRec, *NodePtr;             //\80\80 remove this someday...
 259
 260
 261
 262
 263 //// Tree Path Table - constructed by SearchTree, used by InsertTree and DeleteTree
 264
 265 typedef struct {
 266         u_int32_t                               node;                           // node number
 267         u_int16_t                               index;
 268         u_int16_t                               reserved;                       // align size to a power of 2
 269 } TreePathRecord, *TreePathRecordPtr;
 270
 271 typedef TreePathRecord          TreePathTable [kMaxTreeDepth];
 272
 273
 274 //// InsertKey - used by InsertTree, InsertLevel and InsertNode
 275
 276 struct InsertKey {
 277         BTreeKeyPtr             keyPtr;
 278         u_int8_t *              recPtr;
 279         u_int16_t               keyLength;
 280         u_int16_t               recSize;
 281         Boolean                 replacingKey;
 282         Boolean                 skipRotate;
 283 };
 284
 285 typedef struct InsertKey InsertKey;
 286
 287
 288 //// For Notational Convenience
 289
 290 typedef BTNodeDescriptor*        NodeDescPtr;
 291 typedef u_int8_t                        *RecordPtr;
 292 typedef BTreeKeyPtr                      KeyPtr;
 293
 294
 295 //////////////////////////////////// Globals ////////////////////////////////////
 296
 297
 298 //////////////////////////////////// Macros /////////////////////////////////////
 299
 300 #if DEBUG
 301         #define Panic( message )                                        DebugStr( message )
 302         #define PanicIf( condition, message )           do { if ( (condition) != 0 )    DebugStr( message ); } while(0)
 303 #else
 304         #define Panic( message )                                do { } while(0)
 305         #define PanicIf( condition, message )   do { } while(0)
 306 #endif
 307
 308 //      Exit function on error
 309 #define M_ExitOnError( result ) do { if ( ( result ) != noErr ) goto ErrorExit; } while(0)
 310
 311 //      Test for passed condition and return if true
 312 #define M_ReturnErrorIf( condition, error )     do { if ( condition )   return( error ); } while(0)
 313
 314 //////////////////////////////// Key Operations /////////////////////////////////
 315
 316 int32_t         CompareKeys                             (BTreeControlBlockPtr    btreePtr,
 317                                                                          KeyPtr                                  searchKey,
 318                                                                          KeyPtr                                  trialKey );
 319
 320 //////////////////////////////// Map Operations /////////////////////////////////
 321
 322 OSStatus        AllocateNode                    (BTreeControlBlockPtr    btreePtr,
 323                                                                          u_int32_t                              *nodeNum);
 324
 325 OSStatus        FreeNode                                (BTreeControlBlockPtr    btreePtr,
 326                                                                          u_int32_t                               nodeNum);
 327
 328 OSStatus        ExtendBTree                             (BTreeControlBlockPtr    btreePtr,
 329                                                                          u_int32_t                               nodes );
 330
 331 u_int32_t       CalcMapBits                             (BTreeControlBlockPtr    btreePtr);
 332
 333
 334 void            BTUpdateReserve                         (BTreeControlBlockPtr btreePtr,
 335                                                          int nodes);
 336
 337 //////////////////////////////// Misc Operations ////////////////////////////////
 338
 339 u_int16_t       CalcKeyRecordSize               (u_int16_t                               keySize,
 340                                                                          u_int16_t                               recSize );
 341
 342 OSStatus        VerifyHeader                    (FCB                                    *filePtr,
 343                                                                          BTHeaderRec                            *header );
 344
 345 OSStatus        UpdateHeader                    (BTreeControlBlockPtr    btreePtr,
 346                                                  Boolean forceWrite );
 347
 348 OSStatus        FindIteratorPosition    (BTreeControlBlockPtr    btreePtr,
 349                                                                          BTreeIteratorPtr                iterator,
 350                                                                          BlockDescriptor                *left,
 351                                                                          BlockDescriptor                *middle,
 352                                                                          BlockDescriptor                *right,
 353                                                                          u_int32_t                              *nodeNum,
 354                                                                          u_int16_t                              *index,
 355                                                                          Boolean                                *foundRecord );
 356
 357 OSStatus        CheckInsertParams               (FCB                                    *filePtr,
 358                                                                          BTreeIterator                  *iterator,
 359                                                                          FSBufferDescriptor             *record,
 360                                                                          u_int16_t                               recordLen );
 361
 362 OSStatus        TrySimpleReplace                (BTreeControlBlockPtr    btreePtr,
 363                                                                          NodeDescPtr                     nodePtr,
 364                                                                          BTreeIterator                  *iterator,
 365                                                                          FSBufferDescriptor             *record,
 366                                                                          u_int16_t                               recordLen,
 367                                                                          Boolean                                *recordInserted );
 368
 369 OSStatus        IsItAHint                               (BTreeControlBlockPtr    btreePtr,
 370                                                                          BTreeIterator                  *iterator,
 371                                                                          Boolean                                *answer );
 372
 373 extern OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr);
 374
 375 //////////////////////////////// Node Operations ////////////////////////////////
 376
 377 //// Node Operations
 378
 379 OSStatus        GetNode                                 (BTreeControlBlockPtr    btreePtr,
 380                                                                          u_int32_t                               nodeNum,
 381                                                                          u_int32_t                               flags,
 382                                                                          NodeRec                                *returnNodePtr );
 383
 384 /* Flags for GetNode() */
 385 #define         kGetNodeHint    0x1             /* If set, the node is being looked up using a hint */
 386
 387 OSStatus        GetLeftSiblingNode              (BTreeControlBlockPtr    btreePtr,
 388                                                                          NodeDescPtr                     node,
 389                                                                          NodeRec                                *left );
 390
 391 #define         GetLeftSiblingNode(btree,node,left)                     GetNode ((btree), ((NodeDescPtr)(node))->bLink, 0, (left))
 392
 393 OSStatus        GetRightSiblingNode             (BTreeControlBlockPtr    btreePtr,
 394                                                                          NodeDescPtr                     node,
 395                                                                          NodeRec                                *right );
 396
 397 #define         GetRightSiblingNode(btree,node,right)           GetNode ((btree), ((NodeDescPtr)(node))->fLink, 0, (right))
 398
 399
 400 OSStatus        GetNewNode                              (BTreeControlBlockPtr    btreePtr,
 401                                                                          u_int32_t                               nodeNum,
 402                                                                          NodeRec                                *returnNodePtr );
 403
 404 OSStatus        ReleaseNode                             (BTreeControlBlockPtr    btreePtr,
 405                                                                          NodePtr                                 nodePtr );
 406
 407 OSStatus        TrashNode                               (BTreeControlBlockPtr    btreePtr,
 408                                                                          NodePtr                                 nodePtr );
 409
 410 OSStatus        UpdateNode                              (BTreeControlBlockPtr    btreePtr,
 411                                                                          NodePtr                                 nodePtr,
 412                                                                          u_int32_t                               transactionID,
 413                                                                          u_int32_t                               flags );
 414
 415 //// Node Buffer Operations
 416
 417 void            ClearNode                               (BTreeControlBlockPtr    btreePtr,
 418                                                                          NodeDescPtr                     node );
 419
 420 u_int16_t       GetNodeDataSize                 (BTreeControlBlockPtr    btreePtr,
 421                                                                          NodeDescPtr                     node );
 422
 423 u_int16_t       GetNodeFreeSize                 (BTreeControlBlockPtr    btreePtr,
 424                                                                          NodeDescPtr                     node );
 425
 426
 427 //// Record Operations
 428
 429 Boolean         InsertRecord                    (BTreeControlBlockPtr    btreePtr,
 430                                                                          NodeDescPtr                     node,
 431                                                                          u_int16_t                               index,
 432                                                                          RecordPtr                               recPtr,
 433                                                                          u_int16_t                               recSize );
 434
 435 Boolean         InsertKeyRecord                 (BTreeControlBlockPtr    btreePtr,
 436                                                                          NodeDescPtr                     node,
 437                                                                          u_int16_t                               index,
 438                                                                          KeyPtr                                  keyPtr,
 439                                                                          u_int16_t                               keyLength,
 440                                                                          RecordPtr                               recPtr,
 441                                                                          u_int16_t                               recSize );
 442
 443 void            DeleteRecord                    (BTreeControlBlockPtr   btree,
 444                                                                          NodeDescPtr                    node,
 445                                                                          u_int16_t                              index );
 446
 447
 448 Boolean         SearchNode                              (BTreeControlBlockPtr    btree,
 449                                                                          NodeDescPtr                     node,
 450                                                                          KeyPtr                                  searchKey,
 451                                                                          u_int16_t                              *index );
 452
 453 OSStatus        GetRecordByIndex                (BTreeControlBlockPtr    btree,
 454                                                                          NodeDescPtr                     node,
 455                                                                          u_int16_t                               index,
 456                                                                          KeyPtr                                 *keyPtr,
 457                                                                          u_int8_t *                             *dataPtr,
 458                                                                          u_int16_t                              *dataSize );
 459
 460 u_int8_t *      GetRecordAddress                (BTreeControlBlockPtr    btree,
 461                                                                          NodeDescPtr                     node,
 462                                                                          u_int16_t                               index );
 463
 464 #define GetRecordAddress(btreePtr,node,index)           ((u_int8_t *)(node) + (*(short *) ((u_int8_t *)(node) + (btreePtr)->nodeSize - ((index) << 1) - kOffsetSize)))
 465
 466
 467 u_int16_t       GetRecordSize                   (BTreeControlBlockPtr    btree,
 468                                                                          NodeDescPtr                     node,
 469                                                                          u_int16_t                               index );
 470
 471 u_int32_t       GetChildNodeNum                 (BTreeControlBlockPtr    btreePtr,
 472                                                                          NodeDescPtr                     nodePtr,
 473                                                                          u_int16_t                               index );
 474
 475 void            MoveRecordsLeft                 (u_int8_t *                              src,
 476                                                                          u_int8_t *                              dst,
 477                                                                          u_int16_t                               bytesToMove );
 478
 479 #define         MoveRecordsLeft(src,dst,bytes)                  bcopy((src),(dst),(bytes))
 480
 481 void            MoveRecordsRight                (u_int8_t *                              src,
 482                                                                          u_int8_t *                              dst,
 483                                                                          u_int16_t                               bytesToMove );
 484
 485 #define         MoveRecordsRight(src,dst,bytes)                 bcopy((src),(dst),(bytes))
 486
 487
 488 //////////////////////////////// Tree Operations ////////////////////////////////
 489
 490 OSStatus        SearchTree                              (BTreeControlBlockPtr    btreePtr,
 491                                                                          BTreeKeyPtr                     keyPtr,
 492                                                                          TreePathTable                   treePathTable,
 493                                                                          u_int32_t                              *nodeNum,
 494                                                                          BlockDescriptor                *nodePtr,
 495                                                                          u_int16_t                              *index );
 496
 497 OSStatus        InsertTree                              (BTreeControlBlockPtr    btreePtr,
 498                                                                          TreePathTable                   treePathTable,
 499                                                                          KeyPtr                                  keyPtr,
 500                                                                          u_int8_t *                              recPtr,
 501                                                                          u_int16_t                               recSize,
 502                                                                          BlockDescriptor                *targetNode,
 503                                                                          u_int16_t                               index,
 504                                                                          u_int16_t                               level,
 505                                                                          Boolean                                 replacingKey,
 506                                                                          u_int32_t                              *insertNode );
 507
 508 OSStatus        DeleteTree                              (BTreeControlBlockPtr    btreePtr,
 509                                                                          TreePathTable                   treePathTable,
 510                                                                          BlockDescriptor                *targetNode,
 511                                                                          u_int16_t                               index,
 512                                                                          u_int16_t                               level );
 513
 514 #endif /* __APPLE_API_PRIVATE */
 515 #endif /* KERNEL */
 516 #endif //__BTREESPRIVATE__