2 * Copyright (c) 2000-2003, 2005-2015 Apple Inc. All rights reserved.
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
31 Contains: Miscellaneous operations for the BTree Module.
33 Version: xxx put the technology version here xxx
35 Written by: Gordon Sheridan and Bill Bruffey
37 Copyright: (c) 1992-1999 by Apple Inc., all rights reserved.
43 Other Contact: Mark Day
45 Technology: File Systems
53 Change History (most recent first):
55 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6.
56 <CS2> 9/4/97 djb Optimize TrySimpleReplace for the case where record size is not
58 <CS1> 4/23/97 djb first checked in
60 <HFS7> 3/31/97 djb Move ClearMemory to Utilities.c.
61 <HFS6> 3/17/97 DSH Casting for DFA
62 <HFS5> 2/27/97 msd Remove temporary fix from last revision. BTree EOF's should be
63 correct now, so check for strict equality.
64 <HFS4> 2/26/97 msd Fix a casting problem in ClearMemory. TEMPORARY FIX: Made
65 VerifyHeader more lenient, allowing the EOF to be greater than
66 the amount actually used by nodes; this should really be fixed
67 in the formatting code (which needs to compute the real BTree
68 sizes before writing the volume header).
69 <HFS3> 2/19/97 djb Added ClearMemory. Changed CalcKeyLength to KeyLength.
70 <HFS2> 1/3/97 djb Added support for large keys.
71 <HFS1> 12/19/96 djb first checked in
73 History applicable to original Scarecrow Design:
75 <9> 10/25/96 ser Changing for new VFPI
76 <8> 10/18/96 ser Converting over VFPI changes
77 <7> 9/17/96 dkh More BTree statistics. Change IsItAHint to not always check to
78 see if the hint node is allocated.
79 <6> 9/16/96 dkh Revised BTree statistics.
80 <5> 6/20/96 dkh Radar #1358740. Change from using Pools to debug MemAllocators.
81 <4> 1/22/96 dkh Change Pools.i inclusion to PoolsPriv.i
82 <3> 1/10/96 msd Change 64-bit math to use real function names from Math64.i.
83 <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress.
84 <1> 10/18/95 rst Moved from Scarecrow project.
86 <19> 4/26/95 prp In UpdateHeader, clear the dirty flag after the BTree is updated.
87 <18> 1/12/95 wjk Adopt Model FileSystem changes in D5.
88 <17> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was
90 <16> 10/5/94 bk add pools.h include file
91 <15> 9/30/94 prp Get in sync with D2 interface changes.
92 <14> 7/22/94 wjk Convert to the new set of header files.
93 <13> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
95 <12> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and
97 <11> 11/23/93 wjk Changes required to compile on the RS6000.
98 <10> 8/31/93 prp Use U64SetU instead of S64Set.
99 <9> 6/2/93 gs Update for changes to FSErrors.h and add some comments.
100 <8> 5/21/93 gs Modify UpdateHeader to write out attributes. Remove
101 Get/UpdateNode from TrySimpleReplace.
102 <7> 5/10/93 gs Add TrySimpleReplace routine.
103 <6> 3/23/93 gs Change MoveData to take void * instead of Ptr. Add UpdateHeader
104 and ClearBytes routines.
105 <5> 2/8/93 gs Add FindIteratorPosition.
106 <4> 12/10/92 gs Implement CheckKeyDescriptor and the KeyDescriptor interpreter.
107 <3> 12/8/92 gs Add GetKeyDescriptor, VerifyHeader, and Alloc/Dealloc memory
109 <2> 12/2/92 gs Add CompareKeys routine.
110 <1> 11/15/92 gs first checked in
114 #include "BTreesPrivate.h"
115 #include "hfs_btreeio.h"
118 ////////////////////////////// Routine Definitions //////////////////////////////
120 /*-------------------------------------------------------------------------------
121 Routine: CalcKeyRecordSize - Return size of combined key/record structure.
123 Function: Rounds keySize and recSize so they will end on word boundaries.
124 Does NOT add size of offset.
126 Input: keySize - length of key (including length field)
127 recSize - length of record data
131 Result: u_int16_t - size of combined key/record that will be inserted in btree
132 -------------------------------------------------------------------------------*/
134 u_int16_t
CalcKeyRecordSize (u_int16_t keySize
,
137 if ( M_IsOdd (keySize
) ) keySize
+= 1; // pad byte
139 if (M_IsOdd (recSize
) ) recSize
+= 1; // pad byte
141 return (keySize
+ recSize
);
146 /*-------------------------------------------------------------------------------
147 Routine: VerifyHeader - Validate fields of the BTree header record.
149 Function: Examines the fields of the BTree header record to determine if the
150 fork appears to contain a valid BTree.
152 Input: forkPtr - pointer to fork control block
153 header - pointer to BTree header
156 Result: noErr - success
158 -------------------------------------------------------------------------------*/
160 OSStatus
VerifyHeader (FCB
*filePtr
,
161 BTHeaderRec
*header
)
164 u_int32_t totalNodes
;
167 switch (header
->nodeSize
) // node size == 512*2^n
176 default: return fsBTInvalidHeaderErr
; //\80\80 E_BadNodeType
179 totalNodes
= header
->totalNodes
;
181 forkSize
= (u_int64_t
)totalNodes
* (u_int64_t
)header
->nodeSize
;
183 if ( forkSize
> (u_int64_t
)filePtr
->fcbEOF
)
184 return fsBTInvalidHeaderErr
;
186 if ( header
->freeNodes
>= totalNodes
)
187 return fsBTInvalidHeaderErr
;
189 if ( header
->rootNode
>= totalNodes
)
190 return fsBTInvalidHeaderErr
;
192 if ( header
->firstLeafNode
>= totalNodes
)
193 return fsBTInvalidHeaderErr
;
195 if ( header
->lastLeafNode
>= totalNodes
)
196 return fsBTInvalidHeaderErr
;
198 if ( header
->treeDepth
> kMaxTreeDepth
)
199 return fsBTInvalidHeaderErr
;
202 /////////////////////////// Check BTree Type ////////////////////////////////
204 switch (header
->btreeType
)
206 case 0: // HFS Type - no Key Descriptor
207 case kUserBTreeType
: // with Key Descriptors etc.
208 case kReservedBTreeType
: // Desktop Mgr BTree ?
211 default: return fsBTUnknownVersionErr
;
219 OSStatus
TreeIsDirty(BTreeControlBlockPtr btreePtr
)
221 return (btreePtr
->flags
& kBTHeaderDirty
);
226 /*-------------------------------------------------------------------------------
227 Routine: UpdateHeader - Write BTreeInfoRec fields to Header node.
229 Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
230 header node if necessary.
232 Input: btreePtr - pointer to BTreeInfoRec
235 Result: noErr - success
237 -------------------------------------------------------------------------------*/
239 OSStatus
UpdateHeader(BTreeControlBlockPtr btreePtr
, Boolean forceWrite
)
242 BlockDescriptor node
;
246 if ((btreePtr
->flags
& kBTHeaderDirty
) == 0) // btree info already flushed
249 err
= GetNode (btreePtr
, kHeaderNodeNum
, 0, &node
);
255 ModifyBlockStart(btreePtr
->fileRefNum
, &node
);
257 header
= (BTHeaderRec
*) ((char *)node
.buffer
+ sizeof(BTNodeDescriptor
));
259 header
->treeDepth
= btreePtr
->treeDepth
;
260 header
->rootNode
= btreePtr
->rootNode
;
261 header
->leafRecords
= btreePtr
->leafRecords
;
262 header
->firstLeafNode
= btreePtr
->firstLeafNode
;
263 header
->lastLeafNode
= btreePtr
->lastLeafNode
;
264 header
->nodeSize
= btreePtr
->nodeSize
; //\80\80 this shouldn't change
265 header
->maxKeyLength
= btreePtr
->maxKeyLength
; //\80\80 neither should this
266 header
->totalNodes
= btreePtr
->totalNodes
;
267 header
->freeNodes
= btreePtr
->freeNodes
;
268 header
->btreeType
= btreePtr
->btreeType
;
270 // ignore header->clumpSize; //\80\80 rename this field?
273 options
= kForceWriteBlock
;
275 options
= kLockTransaction
;
277 err
= UpdateNode (btreePtr
, &node
, 0, options
);
279 btreePtr
->flags
&= (~kBTHeaderDirty
);
286 /*-------------------------------------------------------------------------------
287 Routine: FindIteratorPosition - One_line_description.
289 Function: Brief_description_of_the_function_and_any_side_effects
291 Algorithm: see FSC.BT.BTIterateRecord.PICT
293 Note: //\80\80 document side-effects of bad node hints
295 Input: btreePtr - description
296 iterator - description
299 Output: iterator - description
303 nodeNum - description
304 returnIndex - description
305 foundRecord - description
308 Result: noErr - success
310 -------------------------------------------------------------------------------*/
312 OSStatus
FindIteratorPosition (BTreeControlBlockPtr btreePtr
,
313 BTreeIteratorPtr iterator
,
314 BlockDescriptor
*left
,
315 BlockDescriptor
*middle
,
316 BlockDescriptor
*right
,
317 u_int32_t
*returnNodeNum
,
318 u_int16_t
*returnIndex
,
319 Boolean
*foundRecord
)
324 u_int16_t leftIndex
, index
, rightIndex
;
327 // assume btreePtr valid
328 // assume left, middle, right point to BlockDescriptors
329 // assume nodeNum points to u_int32_t
330 // assume index points to u_int16_t
331 // assume foundRecord points to Boolean
334 left
->blockHeader
= nil
;
335 middle
->buffer
= nil
;
336 middle
->blockHeader
= nil
;
338 right
->blockHeader
= nil
;
342 if (iterator
== nil
) // do we have an iterator?
344 err
= fsBTInvalidIteratorErr
;
348 err
= IsItAHint (btreePtr
, iterator
, &validHint
);
351 nodeNum
= iterator
->hint
.nodeNum
;
352 if (! validHint
) // does the hint appear to be valid?
357 err
= GetNode (btreePtr
, nodeNum
, kGetNodeHint
, middle
);
358 if( err
== fsBTInvalidNodeErr
) // returned if nodeNum is out of range
363 if ( ((NodeDescPtr
) middle
->buffer
)->kind
!= kBTLeafNode
||
364 ((NodeDescPtr
) middle
->buffer
)->numRecords
<= 0 )
369 foundIt
= SearchNode (btreePtr
, middle
->buffer
, &iterator
->key
, &index
);
372 ++btreePtr
->numValidHints
;
375 iterator
->hint
.nodeNum
= 0;
379 if (((NodeDescPtr
) middle
->buffer
)->bLink
== 0) // before 1st btree record
384 nodeNum
= ((NodeDescPtr
) middle
->buffer
)->bLink
;
386 // BTree nodes are always grabbed in left to right order.
387 // Therefore release the current node before looking up the
389 err
= ReleaseNode(btreePtr
, middle
);
392 // Look up the left node
393 err
= GetNode (btreePtr
, nodeNum
, 0, left
);
396 // Look up the current node again
397 err
= GetRightSiblingNode (btreePtr
, left
->buffer
, middle
);
400 if ( ((NodeDescPtr
) left
->buffer
)->kind
!= kBTLeafNode
||
401 ((NodeDescPtr
) left
->buffer
)->numRecords
<= 0 )
406 foundIt
= SearchNode (btreePtr
, left
->buffer
, &iterator
->key
, &leftIndex
);
417 if (leftIndex
== 0) // we're lost!
421 else if (leftIndex
>= ((NodeDescPtr
) left
->buffer
)->numRecords
)
423 nodeNum
= ((NodeDescPtr
) left
->buffer
)->fLink
;
425 PanicIf (index
!= 0, "FindIteratorPosition: index != 0"); //\80\80 just checking...
438 else if (index
>= ((NodeDescPtr
) middle
->buffer
)->numRecords
)
440 if (((NodeDescPtr
) middle
->buffer
)->fLink
== 0) // beyond last record
445 nodeNum
= ((NodeDescPtr
) middle
->buffer
)->fLink
;
447 err
= GetRightSiblingNode (btreePtr
, middle
->buffer
, right
);
450 if ( ((NodeDescPtr
) right
->buffer
)->kind
!= kBTLeafNode
||
451 ((NodeDescPtr
) right
->buffer
)->numRecords
<= 0 )
456 foundIt
= SearchNode (btreePtr
, right
->buffer
, &iterator
->key
, &rightIndex
);
457 if (rightIndex
>= ((NodeDescPtr
) right
->buffer
)->numRecords
) // we're lost
461 else // we found it, or rightIndex==0, or rightIndex<numRecs
473 //////////////////////////// Search The Tree ////////////////////////////////
477 TreePathTable treePathTable
; // so we only use stack space if we need to
479 err
= ReleaseNode (btreePtr
, left
); M_ExitOnError (err
);
480 err
= ReleaseNode (btreePtr
, middle
); M_ExitOnError (err
);
481 err
= ReleaseNode (btreePtr
, right
); M_ExitOnError (err
);
483 err
= SearchTree ( btreePtr
, &iterator
->key
, treePathTable
, &nodeNum
, middle
, &index
);
484 switch (err
) //\80\80 separate find condition from exceptions
486 case noErr
: foundIt
= true; break;
487 case fsBTRecordNotFoundErr
: break;
488 default: goto ErrorExit
;
492 /////////////////////////////// Success! ////////////////////////////////////
496 *returnNodeNum
= nodeNum
;
497 *returnIndex
= index
;
498 *foundRecord
= foundIt
;
503 ////////////////////////////// Error Exit ///////////////////////////////////
507 (void) ReleaseNode (btreePtr
, left
);
508 (void) ReleaseNode (btreePtr
, middle
);
509 (void) ReleaseNode (btreePtr
, right
);
513 *foundRecord
= false;
520 /////////////////////////////// CheckInsertParams ///////////////////////////////
522 OSStatus
CheckInsertParams (FCB
*filePtr
,
523 BTreeIterator
*iterator
,
524 FSBufferDescriptor
*record
,
525 u_int16_t recordLen
)
527 BTreeControlBlockPtr btreePtr
;
529 if (filePtr
== nil
) return paramErr
;
531 btreePtr
= (BTreeControlBlockPtr
) filePtr
->fcbBTCBPtr
;
532 if (btreePtr
== nil
) return fsBTInvalidFileErr
;
533 if (iterator
== nil
) return paramErr
;
534 if (record
== nil
) return paramErr
;
536 // check total key/record size limit
537 if ( CalcKeyRecordSize (CalcKeySize(btreePtr
, &iterator
->key
), recordLen
) > (btreePtr
->nodeSize
>> 1))
538 return fsBTRecordTooLargeErr
;
545 /*-------------------------------------------------------------------------------
546 Routine: TrySimpleReplace - Attempts a simple insert, set, or replace.
548 Function: If a hint exitst for the iterator, attempt to find the key in the hint
549 node. If the key is found, an insert operation fails. If the is not
550 found, a replace operation fails. If the key was not found, and the
551 insert position is greater than 0 and less than numRecords, the record
552 is inserted, provided there is enough freeSpace. If the key was found,
553 and there is more freeSpace than the difference between the new record
554 and the old record, the old record is deleted and the new record is
557 Assumptions: iterator key has already been checked by CheckKey
560 Input: btreePtr - description
561 iterator - description
563 recordLen - description
564 operation - description
567 Output: recordInserted - description
570 Result: noErr - success
571 E_RecordExits - insert operation failure
572 != noErr - GetNode, ReleaseNode, UpdateNode returned an error
573 -------------------------------------------------------------------------------*/
575 OSStatus
TrySimpleReplace (BTreeControlBlockPtr btreePtr
,
577 BTreeIterator
*iterator
,
578 FSBufferDescriptor
*record
,
580 Boolean
*recordInserted
)
583 u_int32_t spaceNeeded
;
590 *recordInserted
= false; // we'll assume this won't work...
592 if ( nodePtr
->kind
!= kBTLeafNode
)
593 return noErr
; // we're in the weeds!
595 foundIt
= SearchNode (btreePtr
, nodePtr
, &iterator
->key
, &index
);
597 if ( foundIt
== false )
598 return noErr
; // we might be lost...
600 keySize
= CalcKeySize(btreePtr
, &iterator
->key
); // includes length field
602 spaceNeeded
= CalcKeyRecordSize (keySize
, recordLen
);
604 oldSpace
= GetRecordSize (btreePtr
, nodePtr
, index
);
606 if ( spaceNeeded
== oldSpace
)
610 dst
= GetRecordAddress (btreePtr
, nodePtr
, index
);
612 if ( M_IsOdd (keySize
) )
613 ++keySize
; // add pad byte
615 dst
+= keySize
; // skip over key to point at record
617 BlockMoveData(record
->bufferAddress
, dst
, recordLen
); // blast away...
619 *recordInserted
= true;
621 else if ( (GetNodeFreeSize(btreePtr
, nodePtr
) + oldSpace
) >= spaceNeeded
)
623 DeleteRecord (btreePtr
, nodePtr
, index
);
625 didItFit
= InsertKeyRecord (btreePtr
, nodePtr
, index
,
626 &iterator
->key
, KeyLength(btreePtr
, &iterator
->key
),
627 record
->bufferAddress
, recordLen
);
628 PanicIf (didItFit
== false, "TrySimpleInsert: InsertKeyRecord returned false!");
630 *recordInserted
= true;
632 // else not enough space...
638 /*-------------------------------------------------------------------------------
639 Routine: IsItAHint - checks the hint within a BTreeInterator.
641 Function: checks the hint within a BTreeInterator. If it is non-zero, it may
644 Input: btreePtr - pointer to control block for BTree file
645 iterator - pointer to BTreeIterator
647 Output: answer - true if the hint looks reasonable
648 - false if the hint is 0
650 Result: noErr - success
651 -------------------------------------------------------------------------------*/
654 OSStatus
IsItAHint (BTreeControlBlockPtr btreePtr
, BTreeIterator
*iterator
, Boolean
*answer
)
656 ++btreePtr
->numHintChecks
;
659 if (iterator
->hint
.nodeNum
>= btreePtr
->totalNodes
)
665 if (iterator
->hint
.nodeNum
== 0)
672 ++btreePtr
->numPossibleHints
;