1/*
2 * Copyright (c) 2000-2003, 2005-2009 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:		BTreeAllocate.c
30
31	Contains:	BTree Node Allocation routines 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		(djb)	Don Brady
50		(ser)	Scott Roberts
51		(msd)	Mark Day
52
53	Change History (most recent first):
54
55	   <MOSXS>	  6/1/99	djb		Sync up with Mac OS 8.6.
56	   <CS3>	11/24/97	djb		Remove some debug code (Panic calls).
57	   <CS2>	 7/24/97	djb		CallbackProcs now take refnum instead of an FCB.
58	   <CS1>	 4/23/97	djb		first checked in
59
60	  <HFS2>	 2/19/97	djb		Change E_BadNodeType to fsBTBadNodeType.
61	  <HFS1>	12/19/96	djb		first checked in
62
63	History applicable to original Scarecrow Design:
64
65		 <4>	10/25/96	ser		Changing for new VFPI
66		 <3>	10/18/96	ser		Converting over VFPI changes
67		 <2>	 1/10/96	msd		Change 64-bit math to use real function names from Math64.i.
68		 <1>	10/18/95	rst		Moved from Scarecrow project.
69
70		 <8>	 1/12/95	wjk		Adopt Model FileSystem changes in D5.
71		 <7>	 9/30/94	prp		Get in sync with D2 interface changes.
72		 <6>	 7/22/94	wjk		Convert to the new set of header files.
73		 <5>	 8/31/93	prp		Use U64SetU instead of S64Set.
74		 <4>	 5/21/93	gs		Fix ExtendBTree bug.
75		 <3>	 5/10/93	gs		Fix pointer arithmetic bug in AllocateNode.
76		 <2>	 3/23/93	gs		finish ExtendBTree routine.
77		 <1>	  2/8/93	gs		first checked in
78		 <0>	  1/1/93	gs		begin AllocateNode and FreeNode
79
80*/
81
82#include "../../hfs_btreeio.h"
83#include "../../hfs_endian.h"
84#include "../headers/BTreesPrivate.h"
85
86///////////////////// Routines Internal To BTreeAllocate.c //////////////////////
87
88static OSStatus	GetMapNode (BTreeControlBlockPtr	  btreePtr,
89						BlockDescriptor			 *nodePtr,
90						u_int16_t					**mapPtr,
91						u_int16_t					 *mapSize );
92
93/////////////////////////////////////////////////////////////////////////////////
94
95/*-------------------------------------------------------------------------------
96
97Routine:	AllocateNode	-	Find Free Node, Mark It Used, and Return Node Number.
98
99Function:	Searches the map records for the first free node, marks it "in use" and
100			returns the node number found. This routine should really only be called
101			when we know there are free blocks, otherwise it's just a waste of time.
102
103Note:		We have to examine map nodes a word at a time rather than a long word
104			because the External BTree Mgr used map records that were not an integral
105			number of long words. Too bad. In our spare time could develop a more
106			sophisticated algorithm that read map records by long words (and long
107			word aligned) and handled the spare bytes at the beginning and end
108			appropriately.
109
110Input:		btreePtr	- pointer to control block for BTree file
111
112Output:		nodeNum		- number of node allocated
113
114
115Result:		noErr			- success
116			fsBTNoMoreMapNodesErr	- no free blocks were found
117			!= noErr		- failure
118-------------------------------------------------------------------------------*/
119
120OSStatus	AllocateNode (BTreeControlBlockPtr		btreePtr, u_int32_t	*nodeNum)
121{
122	OSStatus		 err;
123	BlockDescriptor	 node;
124	u_int16_t		*mapPtr, *pos;
125	u_int16_t		 mapSize, size;
126	u_int16_t		 freeWord;
127	u_int16_t		 mask;
128	u_int16_t		 bitOffset;
129	u_int32_t		 nodeNumber;
130
131
132	nodeNumber		= 0;				// first node number of header map record
133	node.buffer		= nil;				// clear node.buffer to get header node
134										//	- and for ErrorExit
135	node.blockHeader = nil;
136
137	while (true)
138	{
139		err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize);
140		M_ExitOnError (err);
141
142		// XXXdbg
143		ModifyBlockStart(btreePtr->fileRefNum, &node);
144
145	//////////////////////// Find Word with Free Bit ////////////////////////////
146
147		pos		= mapPtr;
148		size	= mapSize;
149		size  >>= 1;						// convert to number of words
150						//�� assumes mapRecords contain an integral number of words
151
152		while ( size-- )
153		{
154			if ( *pos++ != 0xFFFF )			// assume test fails, and increment pos
155				break;
156		}
157
158		--pos;								// whoa! backup
159
160		if (*pos != 0xFFFF)					// hey, we got one!
161			break;
162
163		nodeNumber += mapSize << 3;			// covert to number of bits (nodes)
164	}
165
166	///////////////////////// Find Free Bit in Word /////////////////////////////
167
168	freeWord	= SWAP_BE16 (*pos);
169	bitOffset	=  15;
170	mask		=  0x8000;
171
172	do {
173		if ( (freeWord & mask) == 0)
174			break;
175		mask >>= 1;
176	} while (--bitOffset);
177
178	////////////////////// Calculate Free Node Number ///////////////////////////
179
180	nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset);	// (pos-mapPtr) = # of words!
181
182
183	///////////////////////// Check for End of Map //////////////////////////////
184
185	if (nodeNumber >= btreePtr->totalNodes)
186	{
187		err = fsBTFullErr;
188		goto ErrorExit;
189	}
190
191	/////////////////////////// Allocate the Node ///////////////////////////////
192
193	*pos |= SWAP_BE16 (mask);				// set the map bit for the node
194
195	err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
196	M_ExitOnError (err);
197
198	--btreePtr->freeNodes;
199	btreePtr->flags |= kBTHeaderDirty;
200
201	/* Account for allocations from node reserve */
202	BTUpdateReserve(btreePtr, 1);
203
204	*nodeNum = nodeNumber;
205
206	return noErr;
207
208////////////////////////////////// Error Exit ///////////////////////////////////
209
210ErrorExit:
211
212	(void) ReleaseNode (btreePtr, &node);
213	*nodeNum = 0;
214
215	return	err;
216}
217
218
219
220/*-------------------------------------------------------------------------------
221
222Routine:	FreeNode	-	Clear allocation bit for node.
223
224Function:	Finds the bit representing the node specified by nodeNum in the node
225			map and clears the bit.
226
227
228Input:		btreePtr	- pointer to control block for BTree file
229			nodeNum		- number of node to mark free
230
231Output:		none
232
233Result:		noErr			- success
234			fsBTNoMoreMapNodesErr	- node number is beyond end of node map
235			!= noErr		- GetNode or ReleaseNode encountered some difficulty
236-------------------------------------------------------------------------------*/
237
238OSStatus	FreeNode (BTreeControlBlockPtr		btreePtr, u_int32_t	nodeNum)
239{
240	OSStatus		 err;
241	BlockDescriptor	 node;
242	u_int32_t		 nodeIndex;
243	u_int16_t		 mapSize;
244	u_int16_t		*mapPos;
245	u_int16_t		 bitOffset;
246
247
248	//////////////////////////// Find Map Record ////////////////////////////////
249	nodeIndex			= 0;				// first node number of header map record
250	node.buffer			= nil;				// invalidate node.buffer to get header node
251	node.blockHeader    = nil;
252
253	while (nodeNum >= nodeIndex)
254	{
255		err = GetMapNode (btreePtr, &node, &mapPos, &mapSize);
256		M_ExitOnError (err);
257
258		nodeIndex += mapSize << 3;			// covert to number of bits (nodes)
259	}
260
261	//////////////////////////// Mark Node Free /////////////////////////////////
262
263	// XXXdbg
264	ModifyBlockStart(btreePtr->fileRefNum, &node);
265
266	nodeNum -= (nodeIndex - (mapSize << 3));			// relative to this map record
267	bitOffset = 15 - (nodeNum & 0x0000000F);			// last 4 bits are bit offset
268	mapPos += nodeNum >> 4;								// point to word containing map bit
269
270    M_SWAP_BE16_ClearBitNum (*mapPos, bitOffset);		// clear it
271
272	err = UpdateNode (btreePtr, &node, 0, kLockTransaction);
273	M_ExitOnError (err);
274
275	++btreePtr->freeNodes;
276	btreePtr->flags |= kBTHeaderDirty;					// how about a macro for this
277
278	return noErr;
279
280ErrorExit:
281
282	(void) ReleaseNode (btreePtr, &node);
283
284	return	err;
285}
286
287
288
289/*-------------------------------------------------------------------------------
290
291Routine:	ExtendBTree	-	Call FSAgent to extend file, and allocate necessary map nodes.
292
293Function:	This routine calls the the FSAgent to extend the end of fork, if necessary,
294			to accomodate the number of nodes requested. It then allocates as many
295			map nodes as are necessary to account for all the nodes in the B*Tree.
296			If newTotalNodes is less than the current number of nodes, no action is
297			taken.
298
299Note:		Internal HFS File Manager BTree Module counts on an integral number of
300			long words in map records, although they are not long word aligned.
301
302Input:		btreePtr		- pointer to control block for BTree file
303			newTotalNodes	- total number of nodes the B*Tree is to extended to
304
305Output:		none
306
307Result:		noErr		- success
308			!= noErr	- failure
309-------------------------------------------------------------------------------*/
310
311OSStatus	ExtendBTree	(BTreeControlBlockPtr	btreePtr,
312						 u_int32_t				newTotalNodes )
313{
314	OSStatus				 err;
315	FCB						*filePtr;
316	FSSize					 minEOF, maxEOF;
317	u_int16_t				 nodeSize;
318	u_int32_t				 oldTotalNodes;
319	u_int32_t				 newMapNodes;
320	u_int32_t				 mapBits, totalMapBits;
321	u_int32_t				 recStartBit;
322	u_int32_t				 nodeNum, nextNodeNum;
323	u_int32_t				 firstNewMapNodeNum, lastNewMapNodeNum;
324	BlockDescriptor			 mapNode, newNode;
325	u_int16_t				*mapPos;
326	u_int16_t				*mapStart;
327	u_int16_t				 mapSize;
328	u_int16_t				 mapNodeRecSize;
329	u_int32_t				 bitInWord, bitInRecord;
330	u_int16_t				 mapIndex;
331
332
333	oldTotalNodes	 	= btreePtr->totalNodes;
334	if (newTotalNodes  <= oldTotalNodes)				// we're done!
335		return	noErr;
336
337	nodeSize			= btreePtr->nodeSize;
338	filePtr				= GetFileControlBlock(btreePtr->fileRefNum);
339
340	mapNode.buffer		= nil;
341	mapNode.blockHeader = nil;
342	newNode.buffer		= nil;
343	newNode.blockHeader = nil;
344
345	mapNodeRecSize	= nodeSize - sizeof(BTNodeDescriptor) - 6;	// 2 bytes of free space (see note)
346
347
348	//////////////////////// Count Bits In Node Map /////////////////////////////
349
350	totalMapBits = 0;
351	do {
352		err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize);
353		M_ExitOnError (err);
354
355		mapBits		= mapSize << 3;				// mapSize (in bytes) * 8
356		recStartBit	= totalMapBits;				// bit number of first bit in map record
357		totalMapBits  += mapBits;
358
359	} while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 );
360
361	if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr))
362		Panic ("ExtendBTree: totalMapBits != CalcMapBits");
363
364	/////////////////////// Extend LEOF If Necessary ////////////////////////////
365
366	minEOF = (u_int64_t)newTotalNodes * (u_int64_t)nodeSize;
367	if ( (u_int64_t)filePtr->fcbEOF < minEOF )
368	{
369		maxEOF = (u_int64_t)0x7fffffffLL * (u_int64_t)nodeSize;
370
371		err = btreePtr->setEndOfForkProc (btreePtr->fileRefNum, minEOF, maxEOF);
372		M_ExitOnError (err);
373	}
374
375
376	//////////////////// Calc New Total Number Of Nodes /////////////////////////
377
378	newTotalNodes = filePtr->fcbEOF / nodeSize;		// hack!
379	// do we wish to perform any verification of newTotalNodes at this point?
380
381	btreePtr->totalNodes	 =  newTotalNodes;		// do we need to update freeNodes here too?
382
383
384	////////////// Calculate Number Of New Map Nodes Required ///////////////////
385
386	newMapNodes		= 0;
387	if (newTotalNodes > totalMapBits)
388	{
389		newMapNodes			= (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1;
390		firstNewMapNodeNum	= oldTotalNodes;
391		lastNewMapNodeNum	= firstNewMapNodeNum + newMapNodes - 1;
392	}
393	else
394	{
395		err = ReleaseNode (btreePtr, &mapNode);
396		M_ExitOnError (err);
397
398		goto Success;
399	}
400
401
402	/////////////////////// Initialize New Map Nodes ////////////////////////////
403	// XXXdbg - this is the correct place for this:
404	ModifyBlockStart(btreePtr->fileRefNum, &mapNode);
405
406	((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum;
407
408	nodeNum		= firstNewMapNodeNum;
409	while (true)
410	{
411		err = GetNewNode (btreePtr, nodeNum, &newNode);
412		M_ExitOnError (err);
413
414		// XXXdbg
415		ModifyBlockStart(btreePtr->fileRefNum, &newNode);
416
417		((NodeDescPtr)newNode.buffer)->numRecords	= 1;
418		((NodeDescPtr)newNode.buffer)->kind = kBTMapNode;
419
420		// set free space offset
421		*(u_int16_t *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6;
422
423		if (nodeNum++ == lastNewMapNodeNum)
424			break;
425
426		((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum;	// point to next map node
427
428		err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
429		M_ExitOnError (err);
430	}
431
432	err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction);
433	M_ExitOnError (err);
434
435
436	///////////////////// Mark New Map Nodes Allocated //////////////////////////
437
438	nodeNum = firstNewMapNodeNum;
439	do {
440		bitInRecord	= nodeNum - recStartBit;
441
442		while (bitInRecord >= mapBits)
443		{
444			nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink;
445			if ( nextNodeNum == 0)
446			{
447				err = fsBTNoMoreMapNodesErr;
448				goto ErrorExit;
449			}
450
451			err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
452			M_ExitOnError (err);
453
454			err = GetNode (btreePtr, nextNodeNum, 0, &mapNode);
455			M_ExitOnError (err);
456
457			// XXXdbg
458			ModifyBlockStart(btreePtr->fileRefNum, &mapNode);
459
460			mapIndex = 0;
461
462			mapStart	 = (u_int16_t *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex);
463			mapSize		 = GetRecordSize (btreePtr, mapNode.buffer, mapIndex);
464
465			if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) )
466			{
467				Panic ("ExtendBTree: mapSize != M_MapRecordSize");
468			}
469
470			mapBits		= mapSize << 3;		// mapSize (in bytes) * 8
471			recStartBit	= totalMapBits;		// bit number of first bit in map record
472			totalMapBits  += mapBits;
473
474			bitInRecord	= nodeNum - recStartBit;
475		}
476
477		mapPos		= mapStart + ((nodeNum - recStartBit) >> 4);
478		bitInWord	= 15 - ((nodeNum - recStartBit) & 0x0000000F);
479
480        M_SWAP_BE16_SetBitNum (*mapPos, bitInWord);
481
482		++nodeNum;
483
484	} while (nodeNum <= lastNewMapNodeNum);
485
486	err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction);
487	M_ExitOnError (err);
488
489
490	//////////////////////////////// Success ////////////////////////////////////
491
492Success:
493
494	btreePtr->totalNodes	 =  newTotalNodes;
495	btreePtr->freeNodes		+= (newTotalNodes - oldTotalNodes) - newMapNodes;
496
497	btreePtr->flags			|= kBTHeaderDirty;		//�� how about a macro for this
498
499	/* Force the b-tree header changes to disk */
500	(void) UpdateHeader (btreePtr, true);
501
502	return	noErr;
503
504
505	////////////////////////////// Error Exit ///////////////////////////////////
506
507ErrorExit:
508
509	(void) ReleaseNode (btreePtr, &mapNode);
510	(void) ReleaseNode (btreePtr, &newNode);
511
512	return	err;
513}
514
515
516
517/*-------------------------------------------------------------------------------
518
519Routine:	GetMapNode	-	Get the next map node and pointer to the map record.
520
521Function:	Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases
522			it and gets the next node. If nodePtr->buffer is nil, then the header
523			node is retrieved.
524
525
526Input:		btreePtr	- pointer to control block for BTree file
527			nodePtr		- pointer to a BlockDescriptor of a map node
528
529Output:		nodePtr		- pointer to the BlockDescriptor for the next map node
530			mapPtr		- pointer to the map record within the map node
531			mapSize		- number of bytes in the map record
532
533Result:		noErr			- success
534			fsBTNoMoreMapNodesErr	- we've run out of map nodes
535			fsBTInvalidNodeErr			- bad node, or not node type kMapNode
536			!= noErr		- failure
537-------------------------------------------------------------------------------*/
538
539static
540OSStatus	GetMapNode (BTreeControlBlockPtr	  btreePtr,
541						BlockDescriptor			 *nodePtr,
542						u_int16_t				**mapPtr,
543						u_int16_t				 *mapSize )
544{
545	OSStatus	err;
546	u_int16_t	mapIndex;
547	u_int32_t	nextNodeNum;
548
549	if (nodePtr->buffer != nil)		// if iterator is valid...
550	{
551		nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink;
552		if (nextNodeNum == 0)
553		{
554			err = fsBTNoMoreMapNodesErr;
555			goto ErrorExit;
556		}
557
558		err = ReleaseNode (btreePtr, nodePtr);
559		M_ExitOnError (err);
560
561		err = GetNode (btreePtr, nextNodeNum, 0, nodePtr);
562		M_ExitOnError (err);
563
564		if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode)
565		{
566			err = fsBTBadNodeType;
567			goto ErrorExit;
568		}
569
570		++btreePtr->numMapNodesRead;
571		mapIndex = 0;
572	} else {
573		err = GetNode (btreePtr, kHeaderNodeNum, 0, nodePtr);
574		M_ExitOnError (err);
575
576		if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode)
577		{
578			err = fsBTInvalidHeaderErr;				//�� or fsBTBadNodeType
579			goto ErrorExit;
580		}
581
582		mapIndex = 2;
583	}
584
585
586	*mapPtr		= (u_int16_t *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex);
587	*mapSize	= GetRecordSize (btreePtr, nodePtr->buffer, mapIndex);
588
589	return noErr;
590
591
592ErrorExit:
593
594	(void) ReleaseNode (btreePtr, nodePtr);
595
596	*mapPtr		= nil;
597	*mapSize	= 0;
598
599	return	err;
600}
601
602
603
604////////////////////////////////// CalcMapBits //////////////////////////////////
605
606u_int32_t		CalcMapBits	(BTreeControlBlockPtr	 btreePtr)
607{
608	u_int32_t		mapBits;
609
610	mapBits		= M_HeaderMapRecordSize (btreePtr->nodeSize) << 3;
611
612	while (mapBits < btreePtr->totalNodes)
613		mapBits	+= M_MapRecordSize (btreePtr->nodeSize) << 3;
614
615	return	mapBits;
616}
617
618
619/*-------------------------------------------------------------------------------
620Routine:	BTZeroUnusedNodes
621
622Function:	Write zeros to all nodes in the B-tree that are not currently in use.
623-------------------------------------------------------------------------------*/
624int
625BTZeroUnusedNodes(FCB *filePtr)
626{
627	int						err;
628	vnode_t					vp;
629	BTreeControlBlockPtr	btreePtr;
630	BlockDescriptor			mapNode;
631	buf_t					bp;
632	u_int32_t				nodeNumber;
633	u_int16_t				*mapPtr, *pos;
634	u_int16_t				mapSize, size;
635	u_int16_t				mask;
636	u_int16_t				bitNumber;
637	u_int16_t				word;
638	int						numWritten;
639
640	vp = FTOV(filePtr);
641	btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr;
642	bp = NULL;
643	nodeNumber = 0;
644	mapNode.buffer = nil;
645	mapNode.blockHeader = nil;
646	numWritten = 0;
647
648	/* Iterate over map nodes. */
649	while (true)
650	{
651		err = GetMapNode (btreePtr, &mapNode, &mapPtr, &mapSize);
652		if (err)
653		{
654			err = MacToVFSError(err);
655			goto ErrorExit;
656		}
657
658		pos		= mapPtr;
659		size	= mapSize;
660		size  >>= 1;					/* convert to number of 16-bit words */
661
662		/* Iterate over 16-bit words in the map record. */
663		while (size--)
664		{
665			if (*pos != 0xFFFF)			/* Anything free in this word? */
666			{
667				word = SWAP_BE16(*pos);
668
669				/* Iterate over bits in the word. */
670				for (bitNumber = 0, mask = 0x8000;
671				     bitNumber < 16;
672				     ++bitNumber, mask >>= 1)
673				{
674					if (word & mask)
675						continue;				/* This node is in use. */
676
677					if (nodeNumber + bitNumber >= btreePtr->totalNodes)
678					{
679						/* We've processed all of the nodes. */
680						goto done;
681					}
682
683					/*
684					 * Get a buffer full of zeros and write it to the unused
685					 * node.  Since we'll probably be writing a lot of nodes,
686					 * bypass the journal (to avoid a transaction that's too
687					 * big).  Instead, this behaves more like clearing out
688					 * nodes when extending a B-tree (eg., ClearBTNodes).
689					 */
690					bp = buf_getblk(vp, nodeNumber + bitNumber, btreePtr->nodeSize, 0, 0, BLK_META);
691					if (bp == NULL)
692					{
693						printf("hfs: BTZeroUnusedNodes: unable to read node %u\n", nodeNumber + bitNumber);
694						err = EIO;
695						goto ErrorExit;
696					}
697
698					if (buf_flags(bp) & B_LOCKED) {
699						/*
700						 * This node is already part of a transaction and will be written when
701						 * the transaction is committed, so don't write it here.  If we did, then
702						 * we'd hit a panic in hfs_vnop_bwrite because the B_LOCKED bit is still set.
703						 */
704						buf_brelse(bp);
705						continue;
706					}
707
708					buf_clear(bp);
709					buf_markaged(bp);
710
711					/*
712					 * Try not to hog the buffer cache.  Wait for the write
713					 * every 32 nodes.   If VNOP_BWRITE reports an error, bail out and bubble
714					 * it up to the function calling us.  If we tried to update a read-only
715					 * mount on read-only media, for example, catching the error will let
716					 * us alert the callers of this function that they should maintain
717					 * the mount in read-only mode.
718
719					 */
720					++numWritten;
721					if (numWritten % 32 == 0) {
722						err = VNOP_BWRITE(bp);
723						if (err) {
724							goto ErrorExit;
725						}
726					}
727					else {
728						buf_bawrite(bp);
729					}
730				}
731			}
732
733			/* Go to the next word in the bitmap */
734			++pos;
735			nodeNumber += 16;
736		}
737	}
738
739ErrorExit:
740done:
741	(void) ReleaseNode(btreePtr, &mapNode);
742
743	return err;
744}
745