1/*
2 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_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. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23/*
24	File:		BTreeAllocate.c
25
26	Contains:	BTree Node Allocation routines for the BTree Module.
27
28	Version:	xxx put the technology version here xxx
29
30	Written by:	Gordon Sheridan and Bill Bruffey
31
32	Copyright:	� 1992-1999 by Apple Computer, Inc., all rights reserved.
33*/
34
35#include "BTreePrivate.h"
36#include "hfs_endian.h"
37
38///////////////////// Routines Internal To BTreeAllocate.c //////////////////////
39
40OSStatus	GetMapNode (BTreeControlBlockPtr	  btreePtr,
41						BlockDescriptor			 *nodePtr,
42						UInt16					**mapPtr,
43						UInt16					 *mapSize );
44
45/////////////////////////////////////////////////////////////////////////////////
46
47/*-------------------------------------------------------------------------------
48
49Routine:	AllocateNode	-	Find Free Node, Mark It Used, and Return Node Number.
50
51Function:	Searches the map records for the first free node, marks it "in use" and
52			returns the node number found. This routine should really only be called
53			when we know there are free blocks, otherwise it's just a waste of time.
54
55Note:		We have to examine map nodes a word at a time rather than a long word
56			because the External BTree Mgr used map records that were not an integral
57			number of long words. Too bad. In our spare time could develop a more
58			sophisticated algorithm that read map records by long words (and long
59			word aligned) and handled the spare bytes at the beginning and end
60			appropriately.
61
62Input:		btreePtr	- pointer to control block for BTree file
63
64Output:		nodeNum		- number of node allocated
65
66
67Result:		noErr			- success
68			fsBTNoMoreMapNodesErr	- no free blocks were found
69			!= noErr		- failure
70-------------------------------------------------------------------------------*/
71
72OSStatus	AllocateNode (BTreeControlBlockPtr		btreePtr, UInt32	*nodeNum)
73{
74	OSStatus		 err;
75	BlockDescriptor	 node;
76	UInt16			*mapPtr, *pos;
77	UInt16			 mapSize, size;
78	UInt16			 freeWord;
79	UInt16			 mask;
80	UInt16			 bitOffset;
81	UInt32			 nodeNumber;
82
83
84	nodeNumber		= 0;				// first node number of header map record
85	node.buffer		= nil;				// clear node.buffer to get header node
86										//	- and for ErrorExit
87
88	while (true)
89	{
90		err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
91		M_ExitOnError (err);
92
93	//////////////////////// Find Word with Free Bit ////////////////////////////
94
95		pos		= mapPtr;
96		size	= mapSize;
97		size  >>= 1;						// convert to number of words
98						//�� assumes mapRecords contain an integral number of words
99
100		while ( size-- )
101		{
102			if ( *pos++ != 0xFFFF )			// assume test fails, and increment pos
103				break;
104		}
105
106		--pos;								// whoa! backup
107
108		if (*pos != 0xFFFF)					// hey, we got one!
109			break;
110
111		nodeNumber += mapSize << 3;			// covert to number of bits (nodes)
112	}
113
114	///////////////////////// Find Free Bit in Word /////////////////////////////
115
116	freeWord	= SWAP_BE16 (*pos);
117	bitOffset	=  15;
118	mask		=  0x8000;
119
120	do {
121		if ( (freeWord & mask) == 0)
122			break;
123		mask >>= 1;
124	} while (--bitOffset);
125
126	////////////////////// Calculate Free Node Number ///////////////////////////
127
128	nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset);	// (pos-mapPtr) = # of words!
129
130
131	///////////////////////// Check for End of Map //////////////////////////////
132
133	if (nodeNumber >= btreePtr->totalNodes)
134	{
135		err = fsBTFullErr;
136		goto ErrorExit;
137	}
138
139	/////////////////////////// Allocate the Node ///////////////////////////////
140
141	*pos |= SWAP_BE16 (mask);				// set the map bit for the node
142
143	err = UpdateNode (btreePtr, &node);
144	M_ExitOnError (err);
145
146	--btreePtr->freeNodes;
147	btreePtr->flags |= kBTHeaderDirty;
148	*nodeNum = nodeNumber;
149
150	return noErr;
151
152////////////////////////////////// Error Exit ///////////////////////////////////
153
154ErrorExit:
155
156	(void) ReleaseNode (btreePtr, &node);
157	*nodeNum = 0;
158
159	return	err;
160}
161
162
163
164/*-------------------------------------------------------------------------------
165
166Routine:	FreeNode	-	Clear allocation bit for node.
167
168Function:	Finds the bit representing the node specified by nodeNum in the node
169			map and clears the bit.
170
171
172Input:		btreePtr	- pointer to control block for BTree file
173			nodeNum		- number of node to mark free
174
175Output:		none
176
177Result:		noErr			- success
178			fsBTNoMoreMapNodesErr	- node number is beyond end of node map
179			!= noErr		- GetNode or ReleaseNode encountered some difficulty
180-------------------------------------------------------------------------------*/
181
182OSStatus	FreeNode (BTreeControlBlockPtr		btreePtr, UInt32	nodeNum)
183{
184	OSStatus		 err;
185	BlockDescriptor	 node;
186	UInt32			 nodeIndex;
187	UInt16			 mapSize;
188	UInt16			*mapPos;
189	UInt16			 bitOffset;
190
191
192	//////////////////////////// Find Map Record ////////////////////////////////
193	nodeIndex			= 0;				// first node number of header map record
194	node.buffer			= nil;				// invalidate node.buffer to get header node
195
196	while (nodeNum >= nodeIndex)
197	{
198		err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
199		M_ExitOnError (err);
200
201		nodeIndex += mapSize << 3;			// covert to number of bits (nodes)
202	}
203
204	//////////////////////////// Mark Node Free /////////////////////////////////
205
206	nodeNum -= (nodeIndex - (mapSize << 3));			// relative to this map record
207	bitOffset = 15 - (nodeNum & 0x0000000F);			// last 4 bits are bit offset
208	mapPos += nodeNum >> 4;								// point to word containing map bit
209	M_SWAP_BE16_ClearBitNum (*mapPos, bitOffset);		// clear it
210
211	err = UpdateNode (btreePtr, &node);
212	M_ExitOnError (err);
213
214
215	++btreePtr->freeNodes;
216	btreePtr->flags |= kBTHeaderDirty;					//�� how about a macro for this
217
218	return noErr;
219
220ErrorExit:
221
222	(void) ReleaseNode (btreePtr, &node);
223
224	return	err;
225}
226
227
228
229/*-------------------------------------------------------------------------------
230
231Routine:	ExtendBTree	-	Call FSAgent to extend file, and allocate necessary map nodes.
232
233Function:	This routine calls the the FSAgent to extend the end of fork, if necessary,
234			to accomodate the number of nodes requested. It then allocates as many
235			map nodes as are necessary to account for all the nodes in the B*Tree.
236			If newTotalNodes is less than the current number of nodes, no action is
237			taken.
238
239Note:		Internal HFS File Manager BTree Module counts on an integral number of
240			long words in map records, although they are not long word aligned.
241
242Input:		btreePtr		- pointer to control block for BTree file
243			newTotalNodes	- total number of nodes the B*Tree is to extended to
244
245Output:		none
246
247Result:		noErr		- success
248			!= noErr	- failure
249-------------------------------------------------------------------------------*/
250
251OSStatus	ExtendBTree	(BTreeControlBlockPtr	btreePtr,
252						 UInt32					newTotalNodes )
253{
254	OSStatus				 err;
255	SFCB					*filePtr;
256	FSSize					 minEOF, maxEOF;
257	UInt16					 nodeSize;
258	UInt32					 oldTotalNodes;
259	UInt32					 newMapNodes;
260	UInt32					 mapBits, totalMapBits;
261	UInt32					 recStartBit;
262	UInt32					 nodeNum, nextNodeNum;
263	UInt32					 firstNewMapNodeNum, lastNewMapNodeNum;
264	BlockDescriptor			 mapNode, newNode;
265	UInt16					*mapPos;
266	UInt16					*mapStart;
267	UInt16					 mapSize;
268	UInt16					 mapNodeRecSize;
269	UInt32					 bitInWord, bitInRecord;
270	UInt16					 mapIndex;
271
272
273	oldTotalNodes	 	= btreePtr->totalNodes;
274	if (newTotalNodes  <= oldTotalNodes)				// we're done!
275		return	noErr;
276
277	nodeSize			= btreePtr->nodeSize;
278	filePtr				= btreePtr->fcbPtr;
279
280	mapNode.buffer		= nil;
281	newNode.buffer		= nil;
282
283	mapNodeRecSize	= nodeSize - sizeof(BTNodeDescriptor) - 6;	// 2 bytes of free space (see note)
284
285	//�� update for proper 64 bit arithmetic!!
286
287
288	//////////////////////// Count Bits In Node Map /////////////////////////////
289
290	totalMapBits = 0;
291	do {
292		err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
293		M_ExitOnError (err);
294
295		mapBits		= mapSize << 3;				// mapSize (in bytes) * 8
296		recStartBit	= totalMapBits;				// bit number of first bit in map record
297		totalMapBits  += mapBits;
298
299	} while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
300
301	if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
302		Panic ("\pExtendBTree: totalMapBits != CalcMapBits");
303
304	/////////////////////// Extend LEOF If Necessary ////////////////////////////
305
306	minEOF = (UInt64)newTotalNodes * (UInt64)nodeSize;
307	if ( filePtr->fcbLogicalSize < minEOF )
308	{
309		maxEOF = 0xFFFFFFFFFFFFFFFFULL;
310
311		err = btreePtr->setEndOfForkProc (btreePtr->fcbPtr, minEOF, maxEOF);
312		M_ExitOnError (err);
313	}
314
315
316	//////////////////// Calc New Total Number Of Nodes /////////////////////////
317
318	newTotalNodes = filePtr->fcbLogicalSize / nodeSize;		//�� hack!
319	//�� do we wish to perform any verification of newTotalNodes at this point?
320
321	btreePtr->totalNodes = newTotalNodes;		//�� do we need to update freeNodes here too?
322
323
324	////////////// Calculate Number Of New Map Nodes Required ///////////////////
325
326	newMapNodes		= 0;
327	if (newTotalNodes > totalMapBits)
328	{
329		newMapNodes			= (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
330		firstNewMapNodeNum	= oldTotalNodes;
331		lastNewMapNodeNum	= firstNewMapNodeNum + newMapNodes - 1;
332	}
333	else
334	{
335		err = ReleaseNode (btreePtr, &mapNode);
336		M_ExitOnError (err);
337
338		goto Success;
339	}
340
341
342	/////////////////////// Initialize New Map Nodes ////////////////////////////
343
344	((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
345
346	nodeNum		= firstNewMapNodeNum;
347	while (true)
348	{
349		err = GetNewNode (btreePtr, nodeNum, &newNode);
350		M_ExitOnError (err);
351
352		((NodeDescPtr)newNode.buffer)->numRecords	= 1;
353		((NodeDescPtr)newNode.buffer)->kind			= kBTMapNode;
354
355		// set free space offset
356		*(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
357
358		if (nodeNum++ == lastNewMapNodeNum)
359			break;
360
361		((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum;	// point to next map node
362
363		err = UpdateNode (btreePtr, &newNode);
364		M_ExitOnError (err);
365	}
366
367	err = UpdateNode (btreePtr, &newNode);
368	M_ExitOnError (err);
369
370
371	///////////////////// Mark New Map Nodes Allocated //////////////////////////
372
373	nodeNum = firstNewMapNodeNum;
374	do {
375		bitInRecord	= nodeNum - recStartBit;
376
377		while (bitInRecord >= mapBits)
378		{
379			nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
380			if ( nextNodeNum == 0)
381			{
382				err = fsBTNoMoreMapNodesErr;
383				goto ErrorExit;
384			}
385
386			err = UpdateNode (btreePtr, &mapNode);
387			M_ExitOnError (err);
388
389			err = GetNode (btreePtr, nextNodeNum, &mapNode);
390			M_ExitOnError (err);
391
392			mapIndex = 0;
393
394			mapStart	 = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
395			mapSize		 = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
396
397			if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
398			{
399				Panic ("\pExtendBTree: mapSize != M_MapRecordSize");
400			}
401
402			mapBits		= mapSize << 3;		// mapSize (in bytes) * 8
403			recStartBit	= totalMapBits;		// bit number of first bit in map record
404			totalMapBits  += mapBits;
405
406			bitInRecord	= nodeNum - recStartBit;
407		}
408
409		mapPos		= mapStart + ((nodeNum - recStartBit) >> 4);
410		bitInWord	= 15 - ((nodeNum - recStartBit) & 0x0000000F);
411		M_SWAP_BE16_SetBitNum (*mapPos, bitInWord);
412
413		++nodeNum;
414
415	} while (nodeNum <= lastNewMapNodeNum);
416
417	err = UpdateNode (btreePtr, &mapNode);
418	M_ExitOnError (err);
419
420
421	//////////////////////////////// Success ////////////////////////////////////
422
423Success:
424
425	btreePtr->totalNodes	 =  newTotalNodes;
426	btreePtr->freeNodes		+= (newTotalNodes - oldTotalNodes) - newMapNodes;
427
428	btreePtr->flags			|= kBTHeaderDirty;		//�� how about a macro for this
429
430	return	noErr;
431
432
433	////////////////////////////// Error Exit ///////////////////////////////////
434
435ErrorExit:
436
437	(void) ReleaseNode (btreePtr, &mapNode);
438	(void) ReleaseNode (btreePtr, &newNode);
439
440	return	err;
441}
442
443
444
445/*-------------------------------------------------------------------------------
446
447Routine:	GetMapNode	-	Get the next map node and pointer to the map record.
448
449Function:	Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
450			it and gets the next node. If nodePtr->buffer is nil, then the header
451			node is retrieved.
452
453
454Input:		btreePtr	- pointer to control block for BTree file
455			nodePtr		- pointer to a BlockDescriptor of a map node
456
457Output:		nodePtr		- pointer to the BlockDescriptor for the next map node
458			mapPtr		- pointer to the map record within the map node
459			mapSize		- number of bytes in the map record
460
461Result:		noErr			- success
462			fsBTNoMoreMapNodesErr	- we've run out of map nodes
463			fsBTInvalidNodeErr			- bad node, or not node type kMapNode
464			!= noErr		- failure
465-------------------------------------------------------------------------------*/
466
467OSStatus	GetMapNode (BTreeControlBlockPtr	  btreePtr,
468						BlockDescriptor			 *nodePtr,
469						UInt16					**mapPtr,
470						UInt16					 *mapSize )
471{
472	OSStatus	err;
473	UInt16		mapIndex;
474	UInt32		nextNodeNum;
475
476	if (nodePtr->buffer != nil)		// if iterator is valid...
477	{
478		nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
479		if (nextNodeNum == 0)
480		{
481			err = fsBTNoMoreMapNodesErr;
482			goto ErrorExit;
483		}
484
485		err = ReleaseNode (btreePtr, nodePtr);
486		M_ExitOnError (err);
487
488		err = GetNode (btreePtr, nextNodeNum, nodePtr);
489		M_ExitOnError (err);
490
491		if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
492		{
493			err = fsBTBadNodeType;
494			goto ErrorExit;
495		}
496
497		++btreePtr->numMapNodesRead;
498		mapIndex = 0;
499	} else {
500		err = GetNode (btreePtr, kHeaderNodeNum, nodePtr);
501		M_ExitOnError (err);
502
503		if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
504		{
505			err = fsBTInvalidHeaderErr;				//�� or fsBTBadNodeType
506			goto ErrorExit;
507		}
508
509		mapIndex = 2;
510	}
511
512
513	*mapPtr		= (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
514	*mapSize	= GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
515
516	return noErr;
517
518
519ErrorExit:
520
521	(void) ReleaseNode (btreePtr, nodePtr);
522
523	*mapPtr		= nil;
524	*mapSize	= 0;
525
526	return	err;
527}
528
529
530
531////////////////////////////////// CalcMapBits //////////////////////////////////
532
533UInt32		CalcMapBits	(BTreeControlBlockPtr	 btreePtr)
534{
535	UInt32		mapBits;
536
537	mapBits		= M_HeaderMapRecordSize (btreePtr->nodeSize) << 3;
538
539	while (mapBits < btreePtr->totalNodes)
540		mapBits	+= M_MapRecordSize (btreePtr->nodeSize) << 3;
541
542	return	mapBits;
543}
544