--- /dev/null
+/*
+ * Copyright (c) 2000-2003, 2005-2015 Apple Inc. All rights reserved.
+ *
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
+ *
+ * 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.
+ *
+ * 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, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ *
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
+ */
+/*
+ File: BTreeMiscOps.c
+
+ Contains: Miscellaneous operations for the BTree Module.
+
+ Version: xxx put the technology version here xxx
+
+ Written by: Gordon Sheridan and Bill Bruffey
+
+ Copyright: (c) 1992-1999 by Apple Inc., all rights reserved.
+
+ File Ownership:
+
+ DRI: Don Brady
+
+ Other Contact: Mark Day
+
+ Technology: File Systems
+
+ Writers:
+
+ (DSH) Deric Horn
+ (msd) Mark Day
+ (djb) Don Brady
+
+ Change History (most recent first):
+
+ <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
+ <CS2> 9/4/97 djb Optimize TrySimpleReplace for the case where record size is not
+ changing.
+ <CS1> 4/23/97 djb first checked in
+
+ <HFS7> 3/31/97 djb Move ClearMemory to Utilities.c.
+ <HFS6> 3/17/97 DSH Casting for DFA
+ <HFS5> 2/27/97 msd Remove temporary fix from last revision. BTree EOF's should be
+ correct now, so check for strict equality.
+ <HFS4> 2/26/97 msd Fix a casting problem in ClearMemory. TEMPORARY FIX: Made
+ VerifyHeader more lenient, allowing the EOF to be greater than
+ the amount actually used by nodes; this should really be fixed
+ in the formatting code (which needs to compute the real BTree
+ sizes before writing the volume header).
+ <HFS3> 2/19/97 djb Added ClearMemory. Changed CalcKeyLength to KeyLength.
+ <HFS2> 1/3/97 djb Added support for large keys.
+ <HFS1> 12/19/96 djb first checked in
+
+ History applicable to original Scarecrow Design:
+
+ <9> 10/25/96 ser Changing for new VFPI
+ <8> 10/18/96 ser Converting over VFPI changes
+ <7> 9/17/96 dkh More BTree statistics. Change IsItAHint to not always check to
+ see if the hint node is allocated.
+ <6> 9/16/96 dkh Revised BTree statistics.
+ <5> 6/20/96 dkh Radar #1358740. Change from using Pools to debug MemAllocators.
+ <4> 1/22/96 dkh Change Pools.i inclusion to PoolsPriv.i
+ <3> 1/10/96 msd Change 64-bit math to use real function names from Math64.i.
+ <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress.
+ <1> 10/18/95 rst Moved from Scarecrow project.
+
+ <19> 4/26/95 prp In UpdateHeader, clear the dirty flag after the BTree is updated.
+ <18> 1/12/95 wjk Adopt Model FileSystem changes in D5.
+ <17> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was
+ used for testing.
+ <16> 10/5/94 bk add pools.h include file
+ <15> 9/30/94 prp Get in sync with D2 interface changes.
+ <14> 7/22/94 wjk Convert to the new set of header files.
+ <13> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
+ NRCmds environments.
+ <12> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
+ NRCmds environments.
+ <11> 11/23/93 wjk Changes required to compile on the RS6000.
+ <10> 8/31/93 prp Use U64SetU instead of S64Set.
+ <9> 6/2/93 gs Update for changes to FSErrors.h and add some comments.
+ <8> 5/21/93 gs Modify UpdateHeader to write out attributes. Remove
+ Get/UpdateNode from TrySimpleReplace.
+ <7> 5/10/93 gs Add TrySimpleReplace routine.
+ <6> 3/23/93 gs Change MoveData to take void * instead of Ptr. Add UpdateHeader
+ and ClearBytes routines.
+ <5> 2/8/93 gs Add FindIteratorPosition.
+ <4> 12/10/92 gs Implement CheckKeyDescriptor and the KeyDescriptor interpreter.
+ <3> 12/8/92 gs Add GetKeyDescriptor, VerifyHeader, and Alloc/Dealloc memory
+ routines.
+ <2> 12/2/92 gs Add CompareKeys routine.
+ <1> 11/15/92 gs first checked in
+
+*/
+
+#include "BTreesPrivate.h"
+#include "hfs_btreeio.h"
+
+
+////////////////////////////// Routine Definitions //////////////////////////////
+
+/*-------------------------------------------------------------------------------
+Routine: CalcKeyRecordSize - Return size of combined key/record structure.
+
+Function: Rounds keySize and recSize so they will end on word boundaries.
+ Does NOT add size of offset.
+
+Input: keySize - length of key (including length field)
+ recSize - length of record data
+
+Output: none
+
+Result: u_int16_t - size of combined key/record that will be inserted in btree
+-------------------------------------------------------------------------------*/
+
+u_int16_t CalcKeyRecordSize (u_int16_t keySize,
+ u_int16_t recSize )
+{
+ if ( M_IsOdd (keySize) ) keySize += 1; // pad byte
+
+ if (M_IsOdd (recSize) ) recSize += 1; // pad byte
+
+ return (keySize + recSize);
+}
+
+
+
+/*-------------------------------------------------------------------------------
+Routine: VerifyHeader - Validate fields of the BTree header record.
+
+Function: Examines the fields of the BTree header record to determine if the
+ fork appears to contain a valid BTree.
+
+Input: forkPtr - pointer to fork control block
+ header - pointer to BTree header
+
+
+Result: noErr - success
+ != noErr - failure
+-------------------------------------------------------------------------------*/
+
+OSStatus VerifyHeader (FCB *filePtr,
+ BTHeaderRec *header )
+{
+ u_int64_t forkSize;
+ u_int32_t totalNodes;
+
+
+ switch (header->nodeSize) // node size == 512*2^n
+ {
+ case 512:
+ case 1024:
+ case 2048:
+ case 4096:
+ case 8192:
+ case 16384:
+ case 32768: break;
+ default: return fsBTInvalidHeaderErr; //\80\80 E_BadNodeType
+ }
+
+ totalNodes = header->totalNodes;
+
+ forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize;
+
+ if ( forkSize > (u_int64_t)filePtr->fcbEOF )
+ return fsBTInvalidHeaderErr;
+
+ if ( header->freeNodes >= totalNodes )
+ return fsBTInvalidHeaderErr;
+
+ if ( header->rootNode >= totalNodes )
+ return fsBTInvalidHeaderErr;
+
+ if ( header->firstLeafNode >= totalNodes )
+ return fsBTInvalidHeaderErr;
+
+ if ( header->lastLeafNode >= totalNodes )
+ return fsBTInvalidHeaderErr;
+
+ if ( header->treeDepth > kMaxTreeDepth )
+ return fsBTInvalidHeaderErr;
+
+
+ /////////////////////////// Check BTree Type ////////////////////////////////
+
+ switch (header->btreeType)
+ {
+ case 0: // HFS Type - no Key Descriptor
+ case kUserBTreeType: // with Key Descriptors etc.
+ case kReservedBTreeType: // Desktop Mgr BTree ?
+ break;
+
+ default: return fsBTUnknownVersionErr;
+ }
+
+ return noErr;
+}
+
+
+
+OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr)
+{
+ return (btreePtr->flags & kBTHeaderDirty);
+}
+
+
+
+/*-------------------------------------------------------------------------------
+Routine: UpdateHeader - Write BTreeInfoRec fields to Header node.
+
+Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
+ header node if necessary.
+
+Input: btreePtr - pointer to BTreeInfoRec
+
+
+Result: noErr - success
+ != noErr - failure
+-------------------------------------------------------------------------------*/
+
+OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite)
+{
+ OSStatus err;
+ BlockDescriptor node;
+ BTHeaderRec *header;
+ u_int32_t options;
+
+ if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed
+ return noErr;
+
+ err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
+ if (err != noErr) {
+ return err;
+ }
+
+ // XXXdbg
+ ModifyBlockStart(btreePtr->fileRefNum, &node);
+
+ header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor));
+
+ header->treeDepth = btreePtr->treeDepth;
+ header->rootNode = btreePtr->rootNode;
+ header->leafRecords = btreePtr->leafRecords;
+ header->firstLeafNode = btreePtr->firstLeafNode;
+ header->lastLeafNode = btreePtr->lastLeafNode;
+ header->nodeSize = btreePtr->nodeSize; //\80\80 this shouldn't change
+ header->maxKeyLength = btreePtr->maxKeyLength; //\80\80 neither should this
+ header->totalNodes = btreePtr->totalNodes;
+ header->freeNodes = btreePtr->freeNodes;
+ header->btreeType = btreePtr->btreeType;
+
+ // ignore header->clumpSize; //\80\80 rename this field?
+
+ if (forceWrite)
+ options = kForceWriteBlock;
+ else
+ options = kLockTransaction;
+
+ err = UpdateNode (btreePtr, &node, 0, options);
+
+ btreePtr->flags &= (~kBTHeaderDirty);
+
+ return err;
+}
+
+
+
+/*-------------------------------------------------------------------------------
+Routine: FindIteratorPosition - One_line_description.
+
+Function: Brief_description_of_the_function_and_any_side_effects
+
+Algorithm: see FSC.BT.BTIterateRecord.PICT
+
+Note: //\80\80 document side-effects of bad node hints
+
+Input: btreePtr - description
+ iterator - description
+
+
+Output: iterator - description
+ left - description
+ middle - description
+ right - description
+ nodeNum - description
+ returnIndex - description
+ foundRecord - description
+
+
+Result: noErr - success
+ != noErr - failure
+-------------------------------------------------------------------------------*/
+
+OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr,
+ BTreeIteratorPtr iterator,
+ BlockDescriptor *left,
+ BlockDescriptor *middle,
+ BlockDescriptor *right,
+ u_int32_t *returnNodeNum,
+ u_int16_t *returnIndex,
+ Boolean *foundRecord )
+{
+ OSStatus err;
+ Boolean foundIt;
+ u_int32_t nodeNum;
+ u_int16_t leftIndex, index, rightIndex;
+ Boolean validHint;
+
+ // assume btreePtr valid
+ // assume left, middle, right point to BlockDescriptors
+ // assume nodeNum points to u_int32_t
+ // assume index points to u_int16_t
+ // assume foundRecord points to Boolean
+
+ left->buffer = nil;
+ left->blockHeader = nil;
+ middle->buffer = nil;
+ middle->blockHeader = nil;
+ right->buffer = nil;
+ right->blockHeader = nil;
+
+ foundIt = false;
+
+ if (iterator == nil) // do we have an iterator?
+ {
+ err = fsBTInvalidIteratorErr;
+ goto ErrorExit;
+ }
+
+ err = IsItAHint (btreePtr, iterator, &validHint);
+ M_ExitOnError (err);
+
+ nodeNum = iterator->hint.nodeNum;
+ if (! validHint) // does the hint appear to be valid?
+ {
+ goto SearchTheTree;
+ }
+
+ err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
+ if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range
+ goto SearchTheTree;
+
+ M_ExitOnError (err);
+
+ if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
+ ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
+ {
+ goto SearchTheTree;
+ }
+
+ foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
+ if (foundIt == true)
+ {
+ ++btreePtr->numValidHints;
+ goto SuccessfulExit;
+ }
+ iterator->hint.nodeNum = 0;
+
+ if (index == 0)
+ {
+ if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record
+ {
+ goto SuccessfulExit;
+ }
+
+ nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
+
+ // BTree nodes are always grabbed in left to right order.
+ // Therefore release the current node before looking up the
+ // left node.
+ err = ReleaseNode(btreePtr, middle);
+ M_ExitOnError(err);
+
+ // Look up the left node
+ err = GetNode (btreePtr, nodeNum, 0, left);
+ M_ExitOnError (err);
+
+ // Look up the current node again
+ err = GetRightSiblingNode (btreePtr, left->buffer, middle);
+ M_ExitOnError (err);
+
+ if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
+ ((NodeDescPtr) left->buffer)->numRecords <= 0 )
+ {
+ goto SearchTheTree;
+ }
+
+ foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
+ if (foundIt == true)
+ {
+ *right = *middle;
+ *middle = *left;
+ left->buffer = nil;
+ index = leftIndex;
+
+ goto SuccessfulExit;
+ }
+
+ if (leftIndex == 0) // we're lost!
+ {
+ goto SearchTheTree;
+ }
+ else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
+ {
+ nodeNum = ((NodeDescPtr) left->buffer)->fLink;
+
+ PanicIf (index != 0, "FindIteratorPosition: index != 0"); //\80\80 just checking...
+ goto SuccessfulExit;
+ }
+ else
+ {
+ *right = *middle;
+ *middle = *left;
+ left->buffer = nil;
+ index = leftIndex;
+
+ goto SuccessfulExit;
+ }
+ }
+ else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
+ {
+ if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record
+ {
+ goto SuccessfulExit;
+ }
+
+ nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
+
+ err = GetRightSiblingNode (btreePtr, middle->buffer, right);
+ M_ExitOnError (err);
+
+ if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
+ ((NodeDescPtr) right->buffer)->numRecords <= 0 )
+ {
+ goto SearchTheTree;
+ }
+
+ foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
+ if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost
+ {
+ goto SearchTheTree;
+ }
+ else // we found it, or rightIndex==0, or rightIndex<numRecs
+ {
+ *left = *middle;
+ *middle = *right;
+ right->buffer = nil;
+ index = rightIndex;
+
+ goto SuccessfulExit;
+ }
+ }
+
+
+ //////////////////////////// Search The Tree ////////////////////////////////
+
+SearchTheTree:
+ {
+ TreePathTable treePathTable; // so we only use stack space if we need to
+
+ err = ReleaseNode (btreePtr, left); M_ExitOnError (err);
+ err = ReleaseNode (btreePtr, middle); M_ExitOnError (err);
+ err = ReleaseNode (btreePtr, right); M_ExitOnError (err);
+
+ err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
+ switch (err) //\80\80 separate find condition from exceptions
+ {
+ case noErr: foundIt = true; break;
+ case fsBTRecordNotFoundErr: break;
+ default: goto ErrorExit;
+ }
+ }
+
+ /////////////////////////////// Success! ////////////////////////////////////
+
+SuccessfulExit:
+
+ *returnNodeNum = nodeNum;
+ *returnIndex = index;
+ *foundRecord = foundIt;
+
+ return noErr;
+
+
+ ////////////////////////////// Error Exit ///////////////////////////////////
+
+ErrorExit:
+
+ (void) ReleaseNode (btreePtr, left);
+ (void) ReleaseNode (btreePtr, middle);
+ (void) ReleaseNode (btreePtr, right);
+
+ *returnNodeNum = 0;
+ *returnIndex = 0;
+ *foundRecord = false;
+
+ return err;
+}
+
+
+
+/////////////////////////////// CheckInsertParams ///////////////////////////////
+
+OSStatus CheckInsertParams (FCB *filePtr,
+ BTreeIterator *iterator,
+ FSBufferDescriptor *record,
+ u_int16_t recordLen )
+{
+ BTreeControlBlockPtr btreePtr;
+
+ if (filePtr == nil) return paramErr;
+
+ btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
+ if (btreePtr == nil) return fsBTInvalidFileErr;
+ if (iterator == nil) return paramErr;
+ if (record == nil) return paramErr;
+
+ // check total key/record size limit
+ if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
+ return fsBTRecordTooLargeErr;
+
+ return noErr;
+}
+
+
+
+/*-------------------------------------------------------------------------------
+Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
+
+Function: If a hint exitst for the iterator, attempt to find the key in the hint
+ node. If the key is found, an insert operation fails. If the is not
+ found, a replace operation fails. If the key was not found, and the
+ insert position is greater than 0 and less than numRecords, the record
+ is inserted, provided there is enough freeSpace. If the key was found,
+ and there is more freeSpace than the difference between the new record
+ and the old record, the old record is deleted and the new record is
+ inserted.
+
+Assumptions: iterator key has already been checked by CheckKey
+
+
+Input: btreePtr - description
+ iterator - description
+ record - description
+ recordLen - description
+ operation - description
+
+
+Output: recordInserted - description
+
+
+Result: noErr - success
+ E_RecordExits - insert operation failure
+ != noErr - GetNode, ReleaseNode, UpdateNode returned an error
+-------------------------------------------------------------------------------*/
+
+OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr,
+ NodeDescPtr nodePtr,
+ BTreeIterator *iterator,
+ FSBufferDescriptor *record,
+ u_int16_t recordLen,
+ Boolean *recordInserted )
+{
+ u_int32_t oldSpace;
+ u_int32_t spaceNeeded;
+ u_int16_t index;
+ u_int16_t keySize;
+ Boolean foundIt;
+ Boolean didItFit;
+
+
+ *recordInserted = false; // we'll assume this won't work...
+
+ if ( nodePtr->kind != kBTLeafNode )
+ return noErr; // we're in the weeds!
+
+ foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index);
+
+ if ( foundIt == false )
+ return noErr; // we might be lost...
+
+ keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field
+
+ spaceNeeded = CalcKeyRecordSize (keySize, recordLen);
+
+ oldSpace = GetRecordSize (btreePtr, nodePtr, index);
+
+ if ( spaceNeeded == oldSpace )
+ {
+ u_int8_t * dst;
+
+ dst = GetRecordAddress (btreePtr, nodePtr, index);
+
+ if ( M_IsOdd (keySize) )
+ ++keySize; // add pad byte
+
+ dst += keySize; // skip over key to point at record
+
+ BlockMoveData(record->bufferAddress, dst, recordLen); // blast away...
+
+ *recordInserted = true;
+ }
+ else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
+ {
+ DeleteRecord (btreePtr, nodePtr, index);
+
+ didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
+ &iterator->key, KeyLength(btreePtr, &iterator->key),
+ record->bufferAddress, recordLen);
+ PanicIf (didItFit == false, "TrySimpleInsert: InsertKeyRecord returned false!");
+
+ *recordInserted = true;
+ }
+ // else not enough space...
+
+ return noErr;
+}
+
+
+/*-------------------------------------------------------------------------------
+Routine: IsItAHint - checks the hint within a BTreeInterator.
+
+Function: checks the hint within a BTreeInterator. If it is non-zero, it may
+ possibly be valid.
+
+Input: btreePtr - pointer to control block for BTree file
+ iterator - pointer to BTreeIterator
+
+Output: answer - true if the hint looks reasonable
+ - false if the hint is 0
+
+Result: noErr - success
+-------------------------------------------------------------------------------*/
+
+
+OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
+{
+ ++btreePtr->numHintChecks;
+
+#if DEBUG
+ if (iterator->hint.nodeNum >= btreePtr->totalNodes)
+ {
+ *answer = false;
+ } else
+
+#endif
+ if (iterator->hint.nodeNum == 0)
+ {
+ *answer = false;
+ }
+ else
+ {
+ *answer = true;
+ ++btreePtr->numPossibleHints;
+ }
+
+ return noErr;
+}
projects / apple / hfs.git / blobdiff