xnu-344.49.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 12c2680afe2adcf32449fb4c2d025dfb6dd3dbf7..0061a3900ed7d1184a72877d93f12984e2d852d0 100644 (file)
--- a/bsd/hfs/hfscommon/BTree/BTree.c
+++ b/bsd/hfs/hfscommon/BTree/BTree.c
@@ -3,19 +3,22 @@
  *
  * @APPLE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_LICENSE_HEADER_START@
  * 

- * 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.
+ * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.

  * 
  * 

- * This Original Code and all software distributed under the License are
- * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * 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

  * 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 OR NON-INFRINGEMENT.  Please see the
- * License for the specific language governing rights and limitations
- * under the License.
+ * 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.

  * 
  * @APPLE_LICENSE_HEADER_END@
  */
  * 
  * @APPLE_LICENSE_HEADER_END@
  */


@@ -339,6 +342,20 @@ OSStatus   BTOpenPath                      (FCB                                    *filePtr,
        err = ReleaseNode (btreePtr, &nodeRec);
        M_ExitOnError (err);
 
        err = ReleaseNode (btreePtr, &nodeRec);
        M_ExitOnError (err);
 

+       /*
+        * Under Mac OS, b-tree nodes can be non-contiguous on disk when the
+        * allocation block size is smaller than the b-tree node size.
+        *
+        * If journaling is turned on for this volume we can't deal with this
+        * situation and so we bail out.  If journaling isn't on it's ok as
+        * hfs_strategy_fragmented() deals with it.  Journaling can't support
+        * this because it assumes that if you give it a block that it's
+        * contiguous on disk.
+        */
+       if ( FCBTOHFS(filePtr)->jnl && !NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize) ) {
+               return fsBTInvalidNodeErr;
+       }
+

        //////////////////////////////// Success ////////////////////////////////////
 
        //\80\80 align LEOF to multiple of node size?       - just on close
        //////////////////////////////// Success ////////////////////////////////////
 
        //\80\80 align LEOF to multiple of node size?       - just on close


@@ -456,6 +473,9 @@ OSStatus    BTSearchRecord          (FCB                                            *filePtr,
        if (filePtr == nil)                                                                     return  paramErr;
        if (searchIterator == nil)                                                      return  paramErr;
 
        if (filePtr == nil)                                                                     return  paramErr;
        if (searchIterator == nil)                                                      return  paramErr;
 

+       node.buffer = nil;
+       node.blockHeader = nil;
+

        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        if (btreePtr == nil)                                                            return  fsBTInvalidFileErr;
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        if (btreePtr == nil)                                                            return  fsBTInvalidFileErr;
 


@@ -629,9 +649,12 @@ OSStatus   BTIterateRecord         (FCB                                            *filePtr,
 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 

-       left.buffer             = nil;
-       right.buffer    = nil;
-       node.buffer             = nil;
+       left.buffer               = nil;
+       left.blockHeader  = nil;
+       right.buffer      = nil;
+       right.blockHeader = nil;
+       node.buffer               = nil;
+       node.blockHeader  = nil;

 
 
        if (filePtr == nil)
 
 
        if (filePtr == nil)


@@ -928,9 +951,12 @@ BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator
 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
 
        ////////////////////////// Priliminary Checks ///////////////////////////////
 

-       left.buffer  = nil;
-       right.buffer = nil;
-       node.buffer  = nil;
+       left.buffer       = nil;
+       left.blockHeader  = nil;
+       right.buffer      = nil;
+       right.blockHeader = nil;
+       node.buffer       = nil;
+       node.blockHeader  = nil;

 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 


@@ -1201,10 +1227,10 @@ OSStatus        BTInsertRecord          (FCB                                            *filePtr,
        UInt16                                  index;
        Boolean                                 recordFit;
 
        UInt16                                  index;
        Boolean                                 recordFit;
 

-

        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode

+       nodeRec.blockHeader = nil;

 
        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        if (err != noErr)
 
        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        if (err != noErr)


@@ -1241,6 +1267,9 @@ OSStatus  BTInsertRecord          (FCB                                            *filePtr,
                                                                err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
                                                                M_ExitOnError (err);
 
                                                                err = GetNewNode (btreePtr, insertNodeNum, &nodeRec);
                                                                M_ExitOnError (err);
 

+                                                               // XXXdbg
+                                                               ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

                                                                ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
                                                                ((NodeDescPtr)nodeRec.buffer)->height   = 1;
 
                                                                ((NodeDescPtr)nodeRec.buffer)->kind = kBTLeafNode;
                                                                ((NodeDescPtr)nodeRec.buffer)->height   = 1;
 


@@ -1261,6 +1290,7 @@ OSStatus  BTInsertRecord          (FCB                                            *filePtr,
                                                                btreePtr->rootNode                      = insertNodeNum;
                                                                btreePtr->firstLeafNode         = insertNodeNum;
                                                                btreePtr->lastLeafNode          = insertNodeNum;
                                                                btreePtr->rootNode                      = insertNodeNum;
                                                                btreePtr->firstLeafNode         = insertNodeNum;
                                                                btreePtr->lastLeafNode          = insertNodeNum;

+

                                                                M_BTreeHeaderDirty (btreePtr);
 
                                                                goto Success;
                                                                M_BTreeHeaderDirty (btreePtr);
 
                                                                goto Success;


@@ -1270,6 +1300,9 @@ OSStatus  BTInsertRecord          (FCB                                            *filePtr,
 
        if (index > 0)
        {
 
        if (index > 0)
        {

+               // XXXdbg
+               ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

                recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
                                                                                &iterator->key, KeyLength(btreePtr, &iterator->key),
                                                                                record->bufferAddress, recordLen);
                recordFit = InsertKeyRecord (btreePtr, nodeRec.buffer, index,
                                                                                &iterator->key, KeyLength(btreePtr, &iterator->key),
                                                                                record->bufferAddress, recordLen);


@@ -1308,7 +1341,7 @@ Success:
        ++btreePtr->writeCount;
        ++btreePtr->leafRecords;
        M_BTreeHeaderDirty (btreePtr);
        ++btreePtr->writeCount;
        ++btreePtr->leafRecords;
        M_BTreeHeaderDirty (btreePtr);

-
+               

        // create hint
        iterator->hint.writeCount       = btreePtr->writeCount;
        iterator->hint.nodeNum          = insertNodeNum;
        // create hint
        iterator->hint.writeCount       = btreePtr->writeCount;
        iterator->hint.nodeNum          = insertNodeNum;


@@ -1359,6 +1392,7 @@ OSStatus  BTReplaceRecord         (FCB                                            *filePtr,
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode

+       nodeRec.blockHeader = nil;

 
        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        if (err != noErr)
 
        err = CheckInsertParams (filePtr, iterator, record, recordLen);
        if (err != noErr)


@@ -1380,6 +1414,9 @@ OSStatus  BTReplaceRecord         (FCB                                            *filePtr,
                err = GetNode (btreePtr, insertNodeNum, &nodeRec);
                if( err == noErr )
                {
                err = GetNode (btreePtr, insertNodeNum, &nodeRec);
                if( err == noErr )
                {

+                       // XXXdbg
+                       ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

                        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
                        M_ExitOnError (err);
 
                        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
                        M_ExitOnError (err);
 


@@ -1415,6 +1452,9 @@ OSStatus  BTReplaceRecord         (FCB                                            *filePtr,
        // optimization - if simple replace will work then don't extend btree
        // \80\80 if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
 
        // optimization - if simple replace will work then don't extend btree
        // \80\80 if we tried this before, and failed because it wouldn't fit then we shouldn't try this again...
 

+       // XXXdbg
+       ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+

        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
        M_ExitOnError (err);
 
        err = TrySimpleReplace (btreePtr, nodeRec.buffer, iterator, record, recordLen, &recordFit);
        M_ExitOnError (err);
 


@@ -1441,6 +1481,9 @@ OSStatus  BTReplaceRecord         (FCB                                            *filePtr,
        }
 
 
        }
 
 

+       // XXXdbg
+       ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

        DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
 
        err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,
        DeleteRecord (btreePtr, nodeRec.buffer, index); // delete existing key/record
 
        err = InsertTree (btreePtr, treePathTable, &iterator->key, record->bufferAddress,


@@ -1498,6 +1541,7 @@ BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator,
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode

+       nodeRec.blockHeader = nil;

 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 
 
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
 


@@ -1521,6 +1565,9 @@ BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator,
                                err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
                                M_ExitOnError (err);
 
                                err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
                                M_ExitOnError (err);
 

+                               // XXXdbg
+                               ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

                                err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
                                M_ExitOnError (err);
 
                                err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
                                M_ExitOnError (err);
 


@@ -1553,6 +1600,9 @@ BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator,
        err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
        M_ExitOnError (err);
 
        err = GetRecordByIndex(btreePtr, nodeRec.buffer, index, &keyPtr, &recordPtr, &recordLen);
        M_ExitOnError (err);
 

+       // XXXdbg
+       ModifyBlockStart(btreePtr->fileRefNum, &nodeRec);
+                                                               

        err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
        M_ExitOnError (err);
 
        err = callBackProc(keyPtr, recordPtr, recordLen, callBackState);
        M_ExitOnError (err);
 


@@ -1600,6 +1650,7 @@ OSStatus  BTDeleteRecord          (FCB                                            *filePtr,
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode
        ////////////////////////// Priliminary Checks ///////////////////////////////
 
        nodeRec.buffer = nil;                                   // so we can call ReleaseNode

+       nodeRec.blockHeader = nil;

 
        M_ReturnErrorIf (filePtr == nil,        paramErr);
        M_ReturnErrorIf (iterator == nil,       paramErr);
 
        M_ReturnErrorIf (filePtr == nil,        paramErr);
        M_ReturnErrorIf (iterator == nil,       paramErr);


@@ -1630,7 +1681,7 @@ OSStatus  BTDeleteRecord          (FCB                                            *filePtr,
        ++btreePtr->writeCount;
        --btreePtr->leafRecords;
        M_BTreeHeaderDirty (btreePtr);
        ++btreePtr->writeCount;
        --btreePtr->leafRecords;
        M_BTreeHeaderDirty (btreePtr);

-
+               

        iterator->hint.nodeNum  = 0;
 
        return noErr;
        iterator->hint.nodeNum  = 0;
 
        return noErr;


@@ -1682,7 +1733,16 @@ OSStatus BTGetInformation        (FCB                                    *filePtr,
        return noErr;
 }
 
        return noErr;
 }
 

+// XXXdbg
+__private_extern__
+OSStatus
+BTIsDirty(FCB *filePtr)
+{
+       BTreeControlBlockPtr    btreePtr;

 
 

+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       return TreeIsDirty(btreePtr);
+}

 
 /*-------------------------------------------------------------------------------
 Routine:       BTFlushPath     -       Flush BTreeControlBlock to Header Node.
 
 /*-------------------------------------------------------------------------------
 Routine:       BTFlushPath     -       Flush BTreeControlBlock to Header Node.


@@ -1743,6 +1803,9 @@ BTReloadData(FCB *filePtr)
        BTHeaderRec *header;    
 
 
        BTHeaderRec *header;    
 
 

+       node.buffer = nil;
+       node.blockHeader = nil;
+

        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        if (btreePtr == nil)
                return (fsBTInvalidFileErr);
        btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
        if (btreePtr == nil)
                return (fsBTInvalidFileErr);


@@ -1877,3 +1940,62 @@ 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__
+OSStatus       BTCheckFreeSpace                (FCB                                    *filePtr)
+{
+       BTreeControlBlockPtr    btreePtr;
+       int                                     nodesNeeded, err = noErr;
+
+
+       M_ReturnErrorIf (filePtr == nil,        paramErr);
+
+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+
+       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;
+       
+       if (btreePtr->freeNodes < nodesNeeded) {
+               err = ExtendBTree(btreePtr, nodesNeeded + btreePtr->totalNodes - btreePtr->freeNodes);
+       }
+
+       return err;
+}
+
+
+__private_extern__
+OSStatus       BTHasContiguousNodes    (FCB                                    *filePtr)
+{
+       BTreeControlBlockPtr    btreePtr;
+       int                                     nodesNeeded, err = noErr;
+
+
+       M_ReturnErrorIf (filePtr == nil,        paramErr);
+
+       btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+       
+       REQUIRE_FILE_LOCK(btreePtr->fileRefNum, true);
+
+       M_ReturnErrorIf (btreePtr == nil,       fsBTInvalidFileErr);
+
+       return NodesAreContiguous(FCBTOVCB(filePtr), filePtr, btreePtr->nodeSize);
+}