1/*
2 * Copyright (c) 2000-2003, 2005-2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
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.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
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.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28/*
29	File:		BTreeMiscOps.c
30
31	Contains:	Miscellaneous operations for the BTree Module.
32
33	Version:	xxx put the technology version here xxx
34
35	Written by:	Gordon Sheridan and Bill Bruffey
36
37	Copyright:	� 1992-1999 by Apple Computer, Inc., all rights reserved.
38
39	File Ownership:
40
41		DRI:				Don Brady
42
43		Other Contact:		Mark Day
44
45		Technology:			File Systems
46
47	Writers:
48
49		(DSH)	Deric Horn
50		(msd)	Mark Day
51		(djb)	Don Brady
52
53	Change History (most recent first):
54
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
57									changing.
58	   <CS1>	 4/23/97	djb		first checked in
59
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
72
73	History applicable to original Scarecrow Design:
74
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.
85
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
89									used for testing.
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
94									NRCmds environments.
95		<12>	11/30/93	wjk		Move from Makefiles to BuildFiles. Fit into the ModernOS and
96									NRCmds environments.
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
108									routines.
109		 <2>	 12/2/92	gs		Add CompareKeys routine.
110		 <1>	11/15/92	gs		first checked in
111
112*/
113
114#include "../headers/BTreesPrivate.h"
115#include "../../hfs_btreeio.h"
116
117
118////////////////////////////// Routine Definitions //////////////////////////////
119
120/*-------------------------------------------------------------------------------
121Routine:	CalcKeyRecordSize	-	Return size of combined key/record structure.
122
123Function:	Rounds keySize and recSize so they will end on word boundaries.
124			Does NOT add size of offset.
125
126Input:		keySize		- length of key (including length field)
127			recSize		- length of record data
128
129Output:		none
130
131Result:		u_int16_t	- size of combined key/record that will be inserted in btree
132-------------------------------------------------------------------------------*/
133
134u_int16_t		CalcKeyRecordSize		(u_int16_t				 keySize,
135										 u_int16_t				 recSize )
136{
137	if ( M_IsOdd (keySize) )	keySize += 1;	// pad byte
138
139	if (M_IsOdd (recSize) )		recSize += 1;	// pad byte
140
141	return	(keySize + recSize);
142}
143
144
145
146/*-------------------------------------------------------------------------------
147Routine:	VerifyHeader	-	Validate fields of the BTree header record.
148
149Function:	Examines the fields of the BTree header record to determine if the
150			fork appears to contain a valid BTree.
151
152Input:		forkPtr		- pointer to fork control block
153			header		- pointer to BTree header
154
155
156Result:		noErr		- success
157			!= noErr	- failure
158-------------------------------------------------------------------------------*/
159
160OSStatus	VerifyHeader	(FCB				*filePtr,
161							 BTHeaderRec			 *header )
162{
163	u_int64_t		forkSize;
164	u_int32_t		totalNodes;
165
166
167	switch (header->nodeSize)							// node size == 512*2^n
168	{
169		case   512:
170		case  1024:
171		case  2048:
172		case  4096:
173		case  8192:
174		case 16384:
175		case 32768:		break;
176		default:		return	fsBTInvalidHeaderErr;			//�� E_BadNodeType
177	}
178
179	totalNodes = header->totalNodes;
180
181	forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize;
182
183	if ( forkSize > (u_int64_t)filePtr->fcbEOF )
184		return fsBTInvalidHeaderErr;
185
186	if ( header->freeNodes >= totalNodes )
187		return fsBTInvalidHeaderErr;
188
189	if ( header->rootNode >= totalNodes )
190		return fsBTInvalidHeaderErr;
191
192	if ( header->firstLeafNode >= totalNodes )
193		return fsBTInvalidHeaderErr;
194
195	if ( header->lastLeafNode >= totalNodes )
196		return fsBTInvalidHeaderErr;
197
198	if ( header->treeDepth > kMaxTreeDepth )
199		return fsBTInvalidHeaderErr;
200
201
202	/////////////////////////// Check BTree Type ////////////////////////////////
203
204	switch (header->btreeType)
205	{
206		case	0:					// HFS Type - no Key Descriptor
207		case	kUserBTreeType:		// with Key Descriptors etc.
208		case	kReservedBTreeType:	// Desktop Mgr BTree ?
209									break;
210
211		default:					return fsBTUnknownVersionErr;
212	}
213
214	return noErr;
215}
216
217
218
219__private_extern__
220OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr)
221{
222    return (btreePtr->flags & kBTHeaderDirty);
223}
224
225
226
227/*-------------------------------------------------------------------------------
228Routine:	UpdateHeader	-	Write BTreeInfoRec fields to Header node.
229
230Function:	Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the
231			header node if necessary.
232
233Input:		btreePtr		- pointer to BTreeInfoRec
234
235
236Result:		noErr		- success
237			!= noErr	- failure
238-------------------------------------------------------------------------------*/
239
240OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite)
241{
242	OSStatus				err;
243	BlockDescriptor			node;
244	BTHeaderRec	*header;
245	u_int32_t options;
246
247	if ((btreePtr->flags & kBTHeaderDirty) == 0)			// btree info already flushed
248	return	noErr;
249
250
251	err = GetNode (btreePtr, kHeaderNodeNum, 0, &node );
252	if (err != noErr) {
253		return	err;
254	}
255
256	// XXXdbg
257	ModifyBlockStart(btreePtr->fileRefNum, &node);
258
259	header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor));
260
261	header->treeDepth		= btreePtr->treeDepth;
262	header->rootNode		= btreePtr->rootNode;
263	header->leafRecords		= btreePtr->leafRecords;
264	header->firstLeafNode	= btreePtr->firstLeafNode;
265	header->lastLeafNode	= btreePtr->lastLeafNode;
266	header->nodeSize		= btreePtr->nodeSize;			//�� this shouldn't change
267	header->maxKeyLength	= btreePtr->maxKeyLength;		//�� neither should this
268	header->totalNodes		= btreePtr->totalNodes;
269	header->freeNodes		= btreePtr->freeNodes;
270	header->btreeType		= btreePtr->btreeType;
271
272	// ignore	header->clumpSize;							//�� rename this field?
273
274	if (forceWrite)
275		options = kForceWriteBlock;
276	else
277		options = kLockTransaction;
278
279	err = UpdateNode (btreePtr, &node, 0, options);
280
281	btreePtr->flags &= (~kBTHeaderDirty);
282
283	return	err;
284}
285
286
287
288/*-------------------------------------------------------------------------------
289Routine:	FindIteratorPosition	-	One_line_description.
290
291Function:	Brief_description_of_the_function_and_any_side_effects
292
293Algorithm:	see FSC.BT.BTIterateRecord.PICT
294
295Note:		//�� document side-effects of bad node hints
296
297Input:		btreePtr		- description
298			iterator		- description
299
300
301Output:		iterator		- description
302			left			- description
303			middle			- description
304			right			- description
305			nodeNum			- description
306			returnIndex		- description
307			foundRecord		- description
308
309
310Result:		noErr		- success
311			!= noErr	- failure
312-------------------------------------------------------------------------------*/
313
314OSStatus	FindIteratorPosition	(BTreeControlBlockPtr	 btreePtr,
315									 BTreeIteratorPtr		 iterator,
316									 BlockDescriptor		*left,
317									 BlockDescriptor		*middle,
318									 BlockDescriptor		*right,
319									 u_int32_t				*returnNodeNum,
320									 u_int16_t				*returnIndex,
321									 Boolean				*foundRecord )
322{
323	OSStatus		err;
324	Boolean			foundIt;
325	u_int32_t		nodeNum;
326	u_int16_t		leftIndex,	index,	rightIndex;
327	Boolean			validHint;
328
329	// assume btreePtr valid
330	// assume left, middle, right point to BlockDescriptors
331	// assume nodeNum points to u_int32_t
332	// assume index points to u_int16_t
333	// assume foundRecord points to Boolean
334
335	left->buffer		= nil;
336	left->blockHeader   = nil;
337	middle->buffer		= nil;
338	middle->blockHeader	= nil;
339	right->buffer		= nil;
340	right->blockHeader	= nil;
341
342	foundIt				= false;
343
344	if (iterator == nil)						// do we have an iterator?
345	{
346		err = fsBTInvalidIteratorErr;
347		goto ErrorExit;
348	}
349
350	err = IsItAHint (btreePtr, iterator, &validHint);
351	M_ExitOnError (err);
352
353	nodeNum = iterator->hint.nodeNum;
354	if (! validHint)							// does the hint appear to be valid?
355	{
356		goto SearchTheTree;
357	}
358
359	err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle);
360	if( err == fsBTInvalidNodeErr )	// returned if nodeNum is out of range
361		goto SearchTheTree;
362
363	M_ExitOnError (err);
364
365	if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode ||
366		 ((NodeDescPtr) middle->buffer)->numRecords <= 0 )
367	{
368		goto SearchTheTree;
369	}
370
371	foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index);
372	if (foundIt == true)
373	{
374		++btreePtr->numValidHints;
375		goto SuccessfulExit;
376	}
377	iterator->hint.nodeNum = 0;
378
379	if (index == 0)
380	{
381		if (((NodeDescPtr) middle->buffer)->bLink == 0)		// before 1st btree record
382		{
383			goto SuccessfulExit;
384		}
385
386		nodeNum = ((NodeDescPtr) middle->buffer)->bLink;
387
388		// BTree nodes are always grabbed in left to right order.
389		// Therefore release the current node before looking up the
390		// left node.
391		err = ReleaseNode(btreePtr, middle);
392		M_ExitOnError(err);
393
394		// Look up the left node
395		err = GetNode (btreePtr, nodeNum, 0, left);
396		M_ExitOnError (err);
397
398		// Look up the current node again
399		err = GetRightSiblingNode (btreePtr, left->buffer, middle);
400		M_ExitOnError (err);
401
402		if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode ||
403			 ((NodeDescPtr) left->buffer)->numRecords <= 0 )
404		{
405			goto SearchTheTree;
406		}
407
408		foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex);
409		if (foundIt == true)
410		{
411			*right			= *middle;
412			*middle			= *left;
413			left->buffer	= nil;
414			index			= leftIndex;
415
416			goto SuccessfulExit;
417		}
418
419		if (leftIndex == 0)									// we're lost!
420		{
421			goto SearchTheTree;
422		}
423		else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords)
424		{
425			nodeNum = ((NodeDescPtr) left->buffer)->fLink;
426
427			PanicIf (index != 0, "FindIteratorPosition: index != 0");	//�� just checking...
428			goto SuccessfulExit;
429		}
430		else
431		{
432			*right			= *middle;
433			*middle			= *left;
434			left->buffer	= nil;
435			index			= leftIndex;
436
437			goto SuccessfulExit;
438		}
439	}
440	else if (index >= ((NodeDescPtr) middle->buffer)->numRecords)
441	{
442		if (((NodeDescPtr) middle->buffer)->fLink == 0)	// beyond last record
443		{
444			goto SuccessfulExit;
445		}
446
447		nodeNum = ((NodeDescPtr) middle->buffer)->fLink;
448
449		err = GetRightSiblingNode (btreePtr, middle->buffer, right);
450		M_ExitOnError (err);
451
452		if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode ||
453			 ((NodeDescPtr) right->buffer)->numRecords <= 0 )
454		{
455			goto SearchTheTree;
456		}
457
458		foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex);
459		if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords)		// we're lost
460		{
461			goto SearchTheTree;
462		}
463		else	// we found it, or rightIndex==0, or rightIndex<numRecs
464		{
465			*left			= *middle;
466			*middle			= *right;
467			right->buffer	= nil;
468			index			= rightIndex;
469
470			goto SuccessfulExit;
471		}
472	}
473
474
475	//////////////////////////// Search The Tree ////////////////////////////////
476
477SearchTheTree:
478	{
479		TreePathTable	treePathTable;		// so we only use stack space if we need to
480
481		err = ReleaseNode (btreePtr, left);			M_ExitOnError (err);
482		err = ReleaseNode (btreePtr, middle);		M_ExitOnError (err);
483		err = ReleaseNode (btreePtr, right);		M_ExitOnError (err);
484
485		err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index);
486		switch (err)				//�� separate find condition from exceptions
487		{
488			case noErr:			foundIt = true;				break;
489			case fsBTRecordNotFoundErr:						break;
490			default:				goto ErrorExit;
491		}
492	}
493
494	/////////////////////////////// Success! ////////////////////////////////////
495
496SuccessfulExit:
497
498	*returnNodeNum	= nodeNum;
499	*returnIndex 	= index;
500	*foundRecord	= foundIt;
501
502	return	noErr;
503
504
505	////////////////////////////// Error Exit ///////////////////////////////////
506
507ErrorExit:
508
509	(void)	ReleaseNode (btreePtr, left);
510	(void)	ReleaseNode (btreePtr, middle);
511	(void)	ReleaseNode (btreePtr, right);
512
513	*returnNodeNum	= 0;
514	*returnIndex 	= 0;
515	*foundRecord	= false;
516
517	return	err;
518}
519
520
521
522/////////////////////////////// CheckInsertParams ///////////////////////////////
523
524OSStatus	CheckInsertParams		(FCB						*filePtr,
525									 BTreeIterator				*iterator,
526									 FSBufferDescriptor			*record,
527									 u_int16_t					 recordLen )
528{
529	BTreeControlBlockPtr	btreePtr;
530
531	if (filePtr == nil)									return	paramErr;
532
533	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
534	if (btreePtr == nil)								return	fsBTInvalidFileErr;
535	if (iterator == nil)								return	paramErr;
536	if (record	 == nil)								return	paramErr;
537
538	//	check total key/record size limit
539	if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1))
540		return	fsBTRecordTooLargeErr;
541
542	return	noErr;
543}
544
545
546
547/*-------------------------------------------------------------------------------
548Routine:	TrySimpleReplace	-	Attempts a simple insert, set, or replace.
549
550Function:	If a hint exitst for the iterator, attempt to find the key in the hint
551			node. If the key is found, an insert operation fails. If the is not
552			found, a replace operation fails. If the key was not found, and the
553			insert position is greater than 0 and less than numRecords, the record
554			is inserted, provided there is enough freeSpace.  If the key was found,
555			and there is more freeSpace than the difference between the new record
556			and the old record, the old record is deleted and the new record is
557			inserted.
558
559Assumptions:	iterator key has already been checked by CheckKey
560
561
562Input:		btreePtr		- description
563			iterator		- description
564			record			- description
565			recordLen		- description
566			operation		- description
567
568
569Output:		recordInserted		- description
570
571
572Result:		noErr			- success
573			E_RecordExits		- insert operation failure
574			!= noErr		- GetNode, ReleaseNode, UpdateNode returned an error
575-------------------------------------------------------------------------------*/
576
577OSStatus	TrySimpleReplace		(BTreeControlBlockPtr	 btreePtr,
578									 NodeDescPtr			 nodePtr,
579									 BTreeIterator			*iterator,
580									 FSBufferDescriptor		*record,
581									 u_int16_t				 recordLen,
582									 Boolean				*recordInserted )
583{
584	u_int32_t			oldSpace;
585	u_int32_t			spaceNeeded;
586	u_int16_t			index;
587	u_int16_t			keySize;
588	Boolean				foundIt;
589	Boolean				didItFit;
590
591
592	*recordInserted	= false;								// we'll assume this won't work...
593
594	if ( nodePtr->kind != kBTLeafNode )
595		return	noErr;	// we're in the weeds!
596
597	foundIt	= SearchNode (btreePtr, nodePtr, &iterator->key, &index);
598
599	if ( foundIt == false )
600		return	noErr;	// we might be lost...
601
602	keySize = CalcKeySize(btreePtr, &iterator->key);	// includes length field
603
604	spaceNeeded	= CalcKeyRecordSize (keySize, recordLen);
605
606	oldSpace = GetRecordSize (btreePtr, nodePtr, index);
607
608	if ( spaceNeeded == oldSpace )
609	{
610		u_int8_t *		dst;
611
612		dst = GetRecordAddress (btreePtr, nodePtr, index);
613
614		if ( M_IsOdd (keySize) )
615			++keySize;			// add pad byte
616
617		dst += keySize;		// skip over key to point at record
618
619		BlockMoveData(record->bufferAddress, dst, recordLen);	// blast away...
620
621		*recordInserted = true;
622	}
623	else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded)
624	{
625		DeleteRecord (btreePtr, nodePtr, index);
626
627		didItFit = InsertKeyRecord (btreePtr, nodePtr, index,
628										&iterator->key, KeyLength(btreePtr, &iterator->key),
629										record->bufferAddress, recordLen);
630		PanicIf (didItFit == false, "TrySimpleInsert: InsertKeyRecord returned false!");
631
632		*recordInserted = true;
633	}
634	// else not enough space...
635
636	return	noErr;
637}
638
639
640/*-------------------------------------------------------------------------------
641Routine:	IsItAHint	-	checks the hint within a BTreeInterator.
642
643Function:	checks the hint within a BTreeInterator.  If it is non-zero, it may
644			possibly be valid.
645
646Input:		btreePtr	- pointer to control block for BTree file
647			iterator	- pointer to BTreeIterator
648
649Output:		answer		- true if the hint looks reasonable
650						- false if the hint is 0
651
652Result:		noErr			- success
653-------------------------------------------------------------------------------*/
654
655
656OSStatus	IsItAHint	(BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer)
657{
658	++btreePtr->numHintChecks;
659
660#if DEBUG_BUILD
661	if (iterator->hint.nodeNum >= btreePtr->totalNodes)
662	{
663		*answer = false;
664	} else
665
666#endif
667	if (iterator->hint.nodeNum == 0)
668	{
669		*answer = false;
670	}
671	else
672	{
673		*answer = true;
674		++btreePtr->numPossibleHints;
675	}
676
677	return noErr;
678}
679