]> git.saurik.com Git - apple/xnu.git/blobdiff - bsd/hfs/hfscommon/BTree/BTree.c
projects / apple / xnu.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
xnu-517.12.7.tar.gz
[apple/xnu.git] / bsd / hfs / hfscommon / BTree / BTree.c
diff --git a/bsd/hfs/hfscommon/BTree/BTree.c b/bsd/hfs/hfscommon/BTree/BTree.c
index 0061a3900ed7d1184a72877d93f12984e2d852d0..dc6c30940acdf9ff75165268a9081a863b7f1ea9 100644 (file)
--- a/bsd/hfs/hfscommon/BTree/BTree.c
+++ b/bsd/hfs/hfscommon/BTree/BTree.c
@@ -1,24 +1,21 @@
 /*
 /*
- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2003 Apple Computer, Inc. All rights reserved.
  *
  * @APPLE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_LICENSE_HEADER_START@
  * 
- * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
+ * The contents of this file constitute Original Code as defined in and
+ * are subject to the Apple Public Source License Version 1.1 (the
+ * "License").  You may not use this file except in compliance with the
+ * License.  Please obtain a copy of the License at
+ * http://www.apple.com/publicsource and read it before using this file.
  * 
  * 
- * This file contains Original Code and/or Modifications of Original Code
- * as defined in and that are subject to the Apple Public Source License
- * Version 2.0 (the 'License'). You may not use this file except in
- * compliance with the License. Please obtain a copy of the License at
- * http://www.opensource.apple.com/apsl/ and read it before using this
- * file.
- * 
- * The Original Code and all software distributed under the License are
- * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * This Original Code and all software distributed under the License are
+ * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
- * Please see the License for the specific language governing rights and
- * limitations under the License.
+ * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
+ * License for the specific language governing rights and limitations
+ * under the License.
  * 
  * @APPLE_LICENSE_HEADER_END@
  */
  * 
  * @APPLE_LICENSE_HEADER_END@
  */
@@ -155,6 +152,12 @@
  */
 #define        kNumLeafRecSlack 10             
 
  */
 #define        kNumLeafRecSlack 10             
 
+/* BTree accessor routines */
+extern OSStatus GetBTreeBlock(FileReference vp, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block);
+extern OSStatus SetBTreeBlockSize(FileReference vp, ByteCount blockSize, ItemCount minBlockCount);
+extern OSStatus ExtendBTreeFile(FileReference vp, FSSize minEOF, FSSize maxEOF);
+extern OSStatus ReleaseBTreeBlock(FileReference vp, BlockDescPtr blockPtr, ReleaseBlockOptions options);
+
 //////////////////////////////////// Globals ////////////////////////////////////
 
 
 //////////////////////////////////// Globals ////////////////////////////////////
 
 
@@ -171,9 +174,6 @@ Function:   Create BTree control block for a file, if necessary. Validates the
 
 Input:         filePtr                         - pointer to file to open as a B-tree
                        keyCompareProc          - pointer to client's KeyCompare function
 
 Input:         filePtr                         - pointer to file to open as a B-tree
                        keyCompareProc          - pointer to client's KeyCompare function
-                       getBlockProc            - pointer to client's GetBlock function
-                       releaseBlockProc        - pointer to client's ReleaseBlock function
-                       setEndOfForkProc        - pointer to client's SetEOF function
 
 Result:                noErr                           - success
                        paramErr                        - required ptr was nil
 
 Result:                noErr                           - success
                        paramErr                        - required ptr was nil
@@ -182,12 +182,7 @@ Result:            noErr                           - success
                        != noErr                        - failure
 -------------------------------------------------------------------------------*/
 
                        != noErr                        - failure
 -------------------------------------------------------------------------------*/
 
-OSStatus       BTOpenPath                      (FCB                                    *filePtr,
-                                                                KeyCompareProcPtr               keyCompareProc,
-                                                                GetBlockProcPtr                 getBlockProc,
-                                                                ReleaseBlockProcPtr     releaseBlockProc,
-                                                                SetEndOfForkProcPtr     setEndOfForkProc,
-                                                                SetBlockSizeProcPtr     setBlockSizeProc )
+OSStatus BTOpenPath(FCB *filePtr, KeyCompareProcPtr keyCompareProc)
 {
        OSStatus                                err;
        BTreeControlBlockPtr    btreePtr;
 {
        OSStatus                                err;
        BTreeControlBlockPtr    btreePtr;
@@ -196,21 +191,22 @@ OSStatus  BTOpenPath                      (FCB                                    *filePtr,
 
        ////////////////////// Preliminary Error Checking ///////////////////////////
 
 
        ////////////////////// Preliminary Error Checking ///////////////////////////
 
-       if ( filePtr == nil                             ||
-                getBlockProc == nil            ||
-                releaseBlockProc == nil        ||
-                setEndOfForkProc == nil        ||
-                setBlockSizeProc == nil )
+       if ( filePtr == nil )
        {
                return  paramErr;
        }
 
        {
                return  paramErr;
        }
 
-       if ( filePtr->fcbBTCBPtr != nil )                       // already has a BTreeCB
+       /*
+        * Subsequent opens allow key compare proc to be changed.
+        */
+       if ( filePtr->fcbBTCBPtr != nil && keyCompareProc != nil) {
+               btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+               btreePtr->keyCompareProc = keyCompareProc;
                return noErr;
                return noErr;
+       }
 
 
-                                                                                               // is file large enough to contain header node?
        if ( filePtr->fcbEOF < kMinNodeSize )
        if ( filePtr->fcbEOF < kMinNodeSize )
-               return fsBTInvalidFileErr;                                                      //\80\80 or E_BadHeader?
+               return fsBTInvalidFileErr;
 
 
        //////////////////////// Allocate Control Block /////////////////////////////
 
 
        //////////////////////// Allocate Control Block /////////////////////////////
@@ -222,9 +218,9 @@ OSStatus    BTOpenPath                      (FCB                                    *filePtr,
                return  memFullErr;
        }
 
                return  memFullErr;
        }
 
-       btreePtr->getBlockProc          = getBlockProc;
-       btreePtr->releaseBlockProc      = releaseBlockProc;
-       btreePtr->setEndOfForkProc      = setEndOfForkProc;
+       btreePtr->getBlockProc          = GetBTreeBlock;
+       btreePtr->releaseBlockProc      = ReleaseBTreeBlock;
+       btreePtr->setEndOfForkProc      = ExtendBTreeFile;
        btreePtr->keyCompareProc        = keyCompareProc;
 
        /////////////////////////// Read Header Node ////////////////////////////////
        btreePtr->keyCompareProc        = keyCompareProc;
 
        /////////////////////////// Read Header Node ////////////////////////////////
@@ -236,15 +232,20 @@ OSStatus  BTOpenPath                      (FCB                                    *filePtr,
        /* The minimum node size is the physical block size */
        nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
 
        /* The minimum node size is the physical block size */
        nodeRec.blockSize = VTOHFS(btreePtr->fileRefNum)->hfs_phys_block_size;
 
+       /* Start with the allocation block size for regular files. */
+       if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
+       {
+               nodeRec.blockSize = FCBTOVCB(filePtr)->blockSize;
+       }
        REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
 
        // it is now safe to call M_ExitOnError (err)
 
        REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
 
        // it is now safe to call M_ExitOnError (err)
 
-       err = setBlockSizeProc (btreePtr->fileRefNum, nodeRec.blockSize, 1);
+       err = SetBTreeBlockSize (btreePtr->fileRefNum, nodeRec.blockSize, 1);
        M_ExitOnError (err);
 
 
        M_ExitOnError (err);
 
 
-       err = getBlockProc (btreePtr->fileRefNum,
+       err = GetBTreeBlock(btreePtr->fileRefNum,
                                                kHeaderNodeNum,
                                                kGetBlock,
                                                &nodeRec );
                                                kHeaderNodeNum,
                                                kGetBlock,
                                                &nodeRec );
@@ -278,9 +279,12 @@ OSStatus   BTOpenPath                      (FCB                                    *filePtr,
        btreePtr->maxKeyLength          = header->maxKeyLength;
        btreePtr->totalNodes            = header->totalNodes;
        btreePtr->freeNodes                     = header->freeNodes;
        btreePtr->maxKeyLength          = header->maxKeyLength;
        btreePtr->totalNodes            = header->totalNodes;
        btreePtr->freeNodes                     = header->freeNodes;
-       // ignore                                         header->clumpSize;    //\80\80 rename this field?
+       if (FTOC(filePtr)->c_fileid >= kHFSFirstUserCatalogNodeID)
+               filePtr->ff_clumpsize = header->clumpSize;
        btreePtr->btreeType                     = header->btreeType;
 
        btreePtr->btreeType                     = header->btreeType;
 
+       btreePtr->keyCompareType = header->keyCompareType;
+
        btreePtr->attributes            = header->attributes;
 
        if ( btreePtr->maxKeyLength > 40 )
        btreePtr->attributes            = header->attributes;
 
        if ( btreePtr->maxKeyLength > 40 )
@@ -304,7 +308,7 @@ OSStatus    BTOpenPath                      (FCB                                    *filePtr,
                 * we cannot mount using the current physical block size.
                 */
                if (btreePtr->leafRecords > 0 ||
                 * we cannot mount using the current physical block size.
                 */
                if (btreePtr->leafRecords > 0 ||
-                   VTOHFS(btreePtr->fileRefNum)->hfs_media_writeable)          
+                   VTOHFS(btreePtr->fileRefNum)->hfs_flags & HFS_WRITEABLE_MEDIA)              
                {
                        err = fsBTBadNodeSize;
                        goto ErrorExit;
                {
                        err = fsBTBadNodeSize;
                        goto ErrorExit;
@@ -321,14 +325,14 @@ OSStatus  BTOpenPath                      (FCB                                    *filePtr,
        }
        else
        {
        }
        else
        {
-               err = setBlockSizeProc (btreePtr->fileRefNum, btreePtr->nodeSize, 32);  //\80\80 we should try and get this down to 8
+               err = SetBTreeBlockSize (btreePtr->fileRefNum, btreePtr->nodeSize, 32);
                M_ExitOnError (err);
 
                /*
                 * Need to use kTrashBlock option to force the
                 * buffer cache to read the entire node
                 */
                M_ExitOnError (err);
 
                /*
                 * Need to use kTrashBlock option to force the
                 * buffer cache to read the entire node
                 */
-               err = releaseBlockProc(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
+               err = ReleaseBTreeBlock(btreePtr->fileRefNum, &nodeRec, kTrashBlock);
                ++btreePtr->numReleaseNodes;
                M_ExitOnError (err);
 
                ++btreePtr->numReleaseNodes;
                M_ExitOnError (err);
 
@@ -1255,7 +1259,7 @@ OSStatus  BTInsertRecord          (FCB                                            *filePtr,
 
                case fsBTEmptyErr:      // if tree empty add 1st leaf node
 
 
                case fsBTEmptyErr:      // if tree empty add 1st leaf node
 
-                                                               if (btreePtr->freeNodes == 0)
+                                                               if (BTAvailableNodes(btreePtr) == 0)
                                                                {
                                                                        err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
                                                                        M_ExitOnError (err);
                                                                {
                                                                        err = ExtendBTree (btreePtr, btreePtr->totalNodes + 1);
                                                                        M_ExitOnError (err);
@@ -1317,10 +1321,10 @@ OSStatus        BTInsertRecord          (FCB                                            *filePtr,
 
        /////////////////////// Extend File If Necessary ////////////////////////////
 
 
        /////////////////////// Extend File If Necessary ////////////////////////////
 
-       nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;   //\80\80 math limit
+       nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
        if (nodesNeeded > 0)
        {
        if (nodesNeeded > 0)
        {
-               nodesNeeded += btreePtr->totalNodes;
+               nodesNeeded += (SInt32)btreePtr->totalNodes;
                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
                        ++nodesNeeded;
 
                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
                        ++nodesNeeded;
 
@@ -1469,10 +1473,10 @@ OSStatus        BTReplaceRecord         (FCB                                            *filePtr,
 
        //////////////////////////// Make Some Room /////////////////////////////////
 
 
        //////////////////////////// Make Some Room /////////////////////////////////
 
-       nodesNeeded =  btreePtr->treeDepth + 1 - btreePtr->freeNodes;   //\80\80 math limit
+       nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
        if (nodesNeeded > 0)
        {
        if (nodesNeeded > 0)
        {
-               nodesNeeded += btreePtr->totalNodes;
+               nodesNeeded += (SInt32)btreePtr->totalNodes;
                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
                        ++nodesNeeded;
 
                if (nodesNeeded > CalcMapBits (btreePtr))       // we'll need to add a map node too!
                        ++nodesNeeded;
 
@@ -1480,7 +1484,6 @@ OSStatus  BTReplaceRecord         (FCB                                            *filePtr,
                M_ExitOnError (err);
        }
 
                M_ExitOnError (err);
        }
 
-
        // XXXdbg
        ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
                                                                
        // XXXdbg
        ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
                                                                
@@ -1643,6 +1646,7 @@ OSStatus  BTDeleteRecord          (FCB                                            *filePtr,
        BTreeControlBlockPtr    btreePtr;
        TreePathTable                   treePathTable;
        BlockDescriptor                 nodeRec;
        BTreeControlBlockPtr    btreePtr;
        TreePathTable                   treePathTable;
        BlockDescriptor                 nodeRec;
+       SInt32 nodesNeeded;
        UInt32                                  nodeNum;
        UInt16                                  index;
 
        UInt32                                  nodeNum;
        UInt16                                  index;
 
@@ -1673,6 +1677,19 @@ OSStatus BTDeleteRecord          (FCB                                            *filePtr,
        M_ExitOnError (err);                                    // record must exit for Delete
 
 
        M_ExitOnError (err);                                    // record must exit for Delete
 
 
+       /////////////////////// Extend File If Necessary ////////////////////////////
+
+       nodesNeeded = (SInt32)btreePtr->treeDepth + 1 - BTAvailableNodes(btreePtr);
+       if ((btreePtr->attributes & kBTVariableIndexKeysMask) && (nodesNeeded > 0))
+       {
+               nodesNeeded += (SInt32)btreePtr->totalNodes;
+               if (nodesNeeded > CalcMapBits (btreePtr))
+                       ++nodesNeeded;
+
+               err = ExtendBTree (btreePtr, nodesNeeded);
+               M_ExitOnError (err);
+       }
+
        ///////////////////////////// Delete Record /////////////////////////////////
 
        err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
        ///////////////////////////// Delete Record /////////////////////////////////
 
        err = DeleteTree (btreePtr, treePathTable, &nodeRec, index, 1);
@@ -1728,8 +1745,7 @@ OSStatus  BTGetInformation        (FCB                                    *filePtr,
        info->numNodes          = btreePtr->totalNodes;
        info->numFreeNodes      = btreePtr->freeNodes;
        info->lastfsync         = btreePtr->lastfsync;
        info->numNodes          = btreePtr->totalNodes;
        info->numFreeNodes      = btreePtr->freeNodes;
        info->lastfsync         = btreePtr->lastfsync;
-       info->reserved          = 0;
-
+       info->keyCompareType    = btreePtr->keyCompareType;
        return noErr;
 }
 
        return noErr;
 }
 
@@ -1940,25 +1956,10 @@ OSStatus        BTSetLastSync           (FCB                                    *filePtr,
 }
 
 
 }
 
 
-/*-------------------------------------------------------------------------------
-Routine:       BTCheckFreeSpace
-
-Function:      Makes sure there is enough free space so that a tree operation
-            will succeed.
-
-Input:         fcb     - pointer file control block
-
-Output:                none
-
-Result:                noErr                   - success
-            
--------------------------------------------------------------------------------*/
-
 __private_extern__
 __private_extern__
-OSStatus       BTCheckFreeSpace                (FCB                                    *filePtr)
+OSStatus       BTHasContiguousNodes    (FCB                                    *filePtr)
 {
        BTreeControlBlockPtr    btreePtr;
 {
        BTreeControlBlockPtr    btreePtr;
-       int                                     nodesNeeded, err = noErr;
 
 
        M_ReturnErrorIf (filePtr == nil,        paramErr);
 
 
        M_ReturnErrorIf (filePtr == nil,        paramErr);
@@ -1969,33 +1970,85 @@ OSStatus        BTCheckFreeSpace                (FCB                                    *filePtr)
 
        M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
 
 
        M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
 
-       // XXXdbg this is highly conservative but so much better than
-       //        winding up with turds on your disk.
-       //
-       nodesNeeded = (btreePtr->treeDepth + 1) * 10;
+       return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
+}
+
+
+/*-------------------------------------------------------------------------------
+Routine:       BTGetUserData
+
+Function:      Read the user data area of the b-tree header node.
+
+-------------------------------------------------------------------------------*/
+__private_extern__
+OSStatus
+BTGetUserData(FCB *filePtr, void * dataPtr, int dataSize)
+{
+       BTreeControlBlockPtr btreePtr;
+       BlockDescriptor node;
+       char * offset;
+       OSStatus err;
+
+       if (dataSize > kBTreeHeaderUserBytes)
+               return (EINVAL);
+       node.buffer = nil;
+       node.blockHeader = nil;
+
+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       if (btreePtr == nil)
+               return (fsBTInvalidFileErr);
+
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+
+       err = GetNode(btreePtr, kHeaderNodeNum, &node);
+       if (err)
+               return (err);
        
        
-       if (btreePtr->freeNodes < nodesNeeded) {
-               err = ExtendBTree(btreePtr, nodesNeeded + btreePtr->totalNodes - btreePtr->freeNodes);
-       }
+       offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+       bcopy(offset, dataPtr, dataSize);
 
 
-       return err;
+       (void) ReleaseNode(btreePtr, &node);
+
+       return  (0);
 }
 
 
 }
 
 
+/*-------------------------------------------------------------------------------
+Routine:       BTSetUserData
+
+Function:      Write the user data area of the b-tree header node.
+-------------------------------------------------------------------------------*/
 __private_extern__
 __private_extern__
-OSStatus       BTHasContiguousNodes    (FCB                                    *filePtr)
+OSStatus
+BTSetUserData(FCB *filePtr, void * dataPtr, int dataSize)
 {
 {
-       BTreeControlBlockPtr    btreePtr;
-       int                                     nodesNeeded, err = noErr;
-
+       BTreeControlBlockPtr btreePtr;
+       BlockDescriptor node;
+       char * offset;
+       OSStatus err;
 
 
-       M_ReturnErrorIf (filePtr == nil,        paramErr);
+       if (dataSize > kBTreeHeaderUserBytes)
+               return (EINVAL);
+       node.buffer = nil;
+       node.blockHeader = nil;
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       if (btreePtr == nil)
+               return (fsBTInvalidFileErr);
+
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, false);
+
+       err = GetNode(btreePtr, kHeaderNodeNum, &node);
+       if (err)
+               return (err);
        
        
-       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+       ModifyBlockStart(btreePtr->fileRefNum, &node);
 
 
-       M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
+       offset = (char *)node.buffer + sizeof(BTNodeDescriptor) + sizeof(BTHeaderRec);
+       bcopy(dataPtr, offset, dataSize);
 
 
-       return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
+       err = UpdateNode (btreePtr, &node, 0, 0);
+
+       return  (err);
 }
 }
+
mirror of XNU