X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/9bccf70c0258c7cac2dcb80011b2a964d884c552..43866e378188c25dd1e2208016ab3cbeb086ae6c:/bsd/hfs/hfscommon/BTree/BTree.c diff --git a/bsd/hfs/hfscommon/BTree/BTree.c b/bsd/hfs/hfscommon/BTree/BTree.c index 12c2680af..0061a3900 100644 --- a/bsd/hfs/hfscommon/BTree/BTree.c +++ b/bsd/hfs/hfscommon/BTree/BTree.c @@ -3,19 +3,22 @@ * * @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, - * 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@ */ @@ -339,6 +342,20 @@ OSStatus BTOpenPath (FCB *filePtr, 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 //////////////////////////////////// //€€ 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; + node.buffer = nil; + node.blockHeader = nil; + btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; if (btreePtr == nil) return fsBTInvalidFileErr; @@ -629,9 +649,12 @@ OSStatus BTIterateRecord (FCB *filePtr, ////////////////////////// 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) @@ -928,9 +951,12 @@ BTIterateRecords(FCB *filePtr, BTreeIterationOperation operation, BTreeIterator ////////////////////////// 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; @@ -1201,10 +1227,10 @@ OSStatus BTInsertRecord (FCB *filePtr, UInt16 index; Boolean recordFit; - ////////////////////////// Priliminary Checks /////////////////////////////// nodeRec.buffer = nil; // so we can call ReleaseNode + nodeRec.blockHeader = nil; 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); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); + ((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; + M_BTreeHeaderDirty (btreePtr); goto Success; @@ -1270,6 +1300,9 @@ OSStatus BTInsertRecord (FCB *filePtr, if (index > 0) { + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); + 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); - + // 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 + nodeRec.blockHeader = nil; 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 ) { + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); + 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 // €€ 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); @@ -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, @@ -1498,6 +1541,7 @@ BTUpdateRecord(FCB *filePtr, BTreeIterator *iterator, ////////////////////////// Priliminary Checks /////////////////////////////// nodeRec.buffer = nil; // so we can call ReleaseNode + nodeRec.blockHeader = nil; 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); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); + 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); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &nodeRec); + 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 + nodeRec.blockHeader = nil; 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); - + iterator->hint.nodeNum = 0; return noErr; @@ -1682,7 +1733,16 @@ OSStatus BTGetInformation (FCB *filePtr, 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. @@ -1743,6 +1803,9 @@ BTReloadData(FCB *filePtr) BTHeaderRec *header; + node.buffer = nil; + node.blockHeader = nil; + 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); +}