X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/1c79356b52d46aa6b508fb032f5ae709b1f2897b..8f6c56a50524aa785f7e596d52dddfb331e18961:/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c diff --git a/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c b/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c index 19e831329..fddcf8856 100644 --- a/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c +++ b/bsd/hfs/hfscommon/BTree/BTreeTreeOps.c @@ -1,23 +1,29 @@ /* * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ + * @APPLE_OSREFERENCE_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. + * 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. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * 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@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ /* File: BTreeTreeOps.c @@ -194,63 +200,123 @@ OSStatus SearchTree (BTreeControlBlockPtr btreePtr, UInt16 *returnIndex ) { OSStatus err; - SInt16 level; - UInt32 curNodeNum; + SInt16 level; // Expected depth of current node + UInt32 curNodeNum; // Current node we're searching NodeRec nodeRec; UInt16 index; Boolean keyFound; + SInt8 nodeKind; // Kind of current node (index/leaf) KeyPtr keyPtr; UInt8 * dataPtr; UInt16 dataSize; - if (btreePtr->treeDepth == 0) // is the tree empty? + curNodeNum = btreePtr->rootNode; + level = btreePtr->treeDepth; + + if (level == 0) // is the tree empty? { err = fsBTEmptyErr; goto ErrorExit; } - curNodeNum = btreePtr->rootNode; - //€€ for debugging... treePathTable [0].node = 0; treePathTable [0].index = 0; while (true) { - PanicIf(curNodeNum == 0, "\pSearchTree: curNodeNum is zero!"); - - err = GetNode (btreePtr, curNodeNum, &nodeRec); - if (err != noErr) - { - goto ErrorExit; - } - - keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index); - - level = ((BTNodeDescriptor*)nodeRec.buffer)->height; //€€ or --level; + // + // [2550929] Node number 0 is the header node. It is never a valid + // index or leaf node. If we're ever asked to search through node 0, + // something has gone wrong (typically a bad child node number, or + // we found a node full of zeroes that we thought was an index node). + // + if (curNodeNum == 0) + { +// Panic("\pSearchTree: curNodeNum is zero!"); + err = btBadNode; + goto ErrorExit; + } + + err = GetNode (btreePtr, curNodeNum, &nodeRec); + if (err != noErr) + { + goto ErrorExit; + } - - treePathTable [level].node = curNodeNum; - - if ( ((BTNodeDescriptor*)nodeRec.buffer)->kind == kBTLeafNode) - { - treePathTable [level].index = index; - break; // were done... - } - - if ( (keyFound != true) && (index != 0)) - --index; - - treePathTable [level].index = index; - - GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize); - curNodeNum = *(UInt32 *)dataPtr; - err = ReleaseNode (btreePtr, &nodeRec); - if (err != noErr) - { - goto ErrorExit; - } + // + // [2550929] Sanity check the node height and node type. We expect + // particular values at each iteration in the search. This checking + // quickly finds bad pointers, loops, and other damage to the + // hierarchy of the B-tree. + // + if (((BTNodeDescriptor*)nodeRec.buffer)->height != level) + { +// Panic("\pIncorrect node height"); + err = btBadNode; + goto ReleaseAndExit; + } + nodeKind = ((BTNodeDescriptor*)nodeRec.buffer)->kind; + if (level == 1) + { + // Nodes at level 1 must be leaves, by definition + if (nodeKind != kBTLeafNode) + { + // Panic("\pIncorrect node type: expected leaf"); + err = btBadNode; + goto ReleaseAndExit; + } + } + else + { + // A node at any other depth must be an index node + if (nodeKind != kBTIndexNode) + { +// Panic("\pIncorrect node type: expected index"); + err = btBadNode; + goto ReleaseAndExit; + } + } + + keyFound = SearchNode (btreePtr, nodeRec.buffer, searchKey, &index); + + treePathTable [level].node = curNodeNum; + + if (nodeKind == kBTLeafNode) + { + treePathTable [level].index = index; + break; // were done... + } + + if ( (keyFound != true) && (index != 0)) + --index; + + treePathTable [level].index = index; + + err = GetRecordByIndex (btreePtr, nodeRec.buffer, index, &keyPtr, &dataPtr, &dataSize); + if (err != noErr) + { + // [2550929] If we got an error, it is probably because the index was bad + // (typically a corrupt node that confused SearchNode). Invalidate the node + // so we won't accidentally use the corrupted contents. NOTE: the Mac OS 9 + // sources call this InvalidateNode. + + (void) TrashNode(btreePtr, &nodeRec); + goto ErrorExit; + } + + // Get the child pointer out of this index node. We're now done with the current + // node and can continue the search with the child node. + curNodeNum = *(UInt32 *)dataPtr; + err = ReleaseNode (btreePtr, &nodeRec); + if (err != noErr) + { + goto ErrorExit; + } + + // The child node should be at a level one less than the parent. + --level; } *nodeNum = curNodeNum; @@ -262,6 +328,10 @@ OSStatus SearchTree (BTreeControlBlockPtr btreePtr, else return fsBTRecordNotFoundErr; // searchKey not found, index identifies insert point +ReleaseAndExit: + (void) ReleaseNode(btreePtr, &nodeRec); + // fall into ErrorExit + ErrorExit: *nodeNum = 0; @@ -325,18 +395,23 @@ OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, Boolean insertParent; Boolean updateParent; Boolean newRoot; + InsertKey insertKey; #if defined(applec) && !defined(__SC__) PanicIf ((level == 1) && (((NodeDescPtr)targetNode->buffer)->kind != kBTLeafNode), "\P InsertLevel: non-leaf at level 1! "); #endif leftNode.buffer = nil; + leftNode.blockHeader = nil; targetNodeNum = treePathTable [level].node; insertParent = false; updateParent = false; + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, targetNode); + ////// process first insert ////// - + err = InsertNode (btreePtr, primaryKey, targetNode, targetNodeNum, index, &newNodeNum, &newIndex, &leftNode, &updateParent, &insertParent, &newRoot ); M_ExitOnError (err); @@ -381,6 +456,9 @@ OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, UInt8 * recPtr; UInt16 recSize; + parentNode.buffer = nil; + parentNode.blockHeader = nil; + secondaryKey = nil; PanicIf ( (level == btreePtr->treeDepth), "\p InsertLevel: unfinished insert!?"); @@ -403,6 +481,9 @@ OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, if ( updateParent ) { + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &parentNode); + //€€ debug: check if ptr == targetNodeNum GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize); PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p InsertLevel: parent ptr doesn't match target node!"); @@ -425,7 +506,6 @@ OSStatus InsertLevel (BTreeControlBlockPtr btreePtr, if ( insertParent ) { InsertKey *insertKeyPtr; - InsertKey insertKey; if ( updateParent ) { @@ -463,7 +543,7 @@ ErrorExit: (void) ReleaseNode (btreePtr, targetNode); (void) ReleaseNode (btreePtr, &leftNode); - Panic ("\p InsertLevel: an error occured!"); + Panic ("\p InsertLevel: an error occurred!"); return err; @@ -530,6 +610,8 @@ static OSErr InsertNode (BTreeControlBlockPtr btreePtr, { err = GetNode (btreePtr, leftNodeNum, leftNode); // will be released by caller or a split below M_ExitOnError (err); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, leftNode); } PanicIf ( ((NodeDescPtr) leftNode->buffer)->fLink != node, "\p InsertNode, RotateLeft: invalid sibling link!" ); @@ -578,7 +660,6 @@ static OSErr InsertNode (BTreeControlBlockPtr btreePtr, return noErr; ErrorExit: - (void) ReleaseNode (btreePtr, leftNode); return err; @@ -614,7 +695,11 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, Boolean deleteRequired; Boolean updateRequired; - + // XXXdbg - initialize these to null in case we get an + // error and try to exit before it's initialized + parentNode.buffer = nil; + parentNode.blockHeader = nil; + deleteRequired = false; updateRequired = false; @@ -622,6 +707,9 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, targetNodePtr = targetNode->buffer; PanicIf (targetNodePtr == nil, "\pDeleteTree: targetNode has nil buffer!"); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, targetNode); + DeleteRecord (btreePtr, targetNodePtr, index); //€€ coalesce remaining records? @@ -633,6 +721,9 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, deleteRequired = true; + siblingNode.buffer = nil; + siblingNode.blockHeader = nil; + ////////////////// Get Siblings & Update Links ////////////////////////// siblingNodeNum = targetNodePtr->bLink; // Left Sibling Node @@ -640,6 +731,10 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, { err = GetNode (btreePtr, siblingNodeNum, &siblingNode); M_ExitOnError (err); + + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &siblingNode); + ((NodeDescPtr)siblingNode.buffer)->fLink = targetNodePtr->fLink; err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction); M_ExitOnError (err); @@ -654,6 +749,10 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, { err = GetNode (btreePtr, siblingNodeNum, &siblingNode); M_ExitOnError (err); + + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &siblingNode); + ((NodeDescPtr)siblingNode.buffer)->bLink = targetNodePtr->bLink; err = UpdateNode (btreePtr, &siblingNode, 0, kLockTransaction); M_ExitOnError (err); @@ -669,6 +768,7 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, err = UpdateNode (btreePtr, targetNode, 0, kLockTransaction); M_ExitOnError (err); + err = FreeNode (btreePtr, targetNodeNum); M_ExitOnError (err); } @@ -712,6 +812,9 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, UInt16 recSize; UInt32 insertNode; + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &parentNode); + //€€ debug: check if ptr == targetNodeNum GetRecordByIndex (btreePtr, parentNode.buffer, index, &keyPtr, &recPtr, &recSize); PanicIf( (*(UInt32 *) recPtr) != targetNodeNum, "\p DeleteTree: parent ptr doesn't match targetNodeNum!!"); @@ -741,7 +844,7 @@ OSStatus DeleteTree (BTreeControlBlockPtr btreePtr, return noErr; ErrorExit: - + (void) ReleaseNode (btreePtr, targetNode); (void) ReleaseNode (btreePtr, &parentNode); @@ -762,6 +865,9 @@ static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr, originalRoot = btreePtr->rootNode; + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, blockPtr); + while (true) { if ( ((NodeDescPtr)blockPtr->buffer)->numRecords > 1) @@ -784,6 +890,9 @@ static OSStatus CollapseTree (BTreeControlBlockPtr btreePtr, //// Get New Root Node err = GetNode (btreePtr, btreePtr->rootNode, blockPtr); M_ExitOnError (err); + + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, blockPtr); } if (btreePtr->rootNode != originalRoot) @@ -1046,6 +1155,9 @@ static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr, if ( left != nil ) { + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, leftNode); + left->fLink = newNodeNum; err = UpdateNode (btreePtr, leftNode, 0, kLockTransaction); M_ExitOnError (err); @@ -1057,6 +1169,9 @@ static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr, err = GetNewNode (btreePtr, newNodeNum, leftNode); M_ExitOnError (err); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, leftNode); + left = leftNode->buffer; left->fLink = rightNodeNum; @@ -1081,8 +1196,9 @@ static OSStatus SplitLeft (BTreeControlBlockPtr btreePtr, err = RotateLeft (btreePtr, left, right, index, keyPtr, recPtr, recSize, insertIndex, insertNodeNum, &recordFit, recsRotated); - M_ExitOnError (err); + M_ExitOnError (err); + return noErr; ErrorExit: @@ -1138,6 +1254,9 @@ static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr, Boolean didItFit; UInt16 keyLength; + rootNode.buffer = nil; + rootNode.blockHeader = nil; + PanicIf (leftNode == nil, "\pAddNewRootNode: leftNode == nil"); PanicIf (rightNode == nil, "\pAddNewRootNode: rightNode == nil"); @@ -1150,6 +1269,9 @@ static OSStatus AddNewRootNode (BTreeControlBlockPtr btreePtr, err = GetNewNode (btreePtr, rootNum, &rootNode); M_ExitOnError (err); + // XXXdbg + ModifyBlockStart(btreePtr->fileRefNum, &rootNode); + ((NodeDescPtr)rootNode.buffer)->kind = kBTIndexNode; ((NodeDescPtr)rootNode.buffer)->height = ++btreePtr->treeDepth;