hfscommon/Misc/VolumeAllocation.c

43 					If not contiguous, then allocation may be less than what was
47 					Deallocate a contiguous run of allocation blocks.
69 					At other times, it should be consistent with the total number of allocation blocks in the
85 					and/or create Red-Black Tree allocation tree nodes to correspond
122 					the allocation fails (i.e. it is "all or nothing").  This routine is
127 					contains logic for when to use which of the allocation algorithms,
143 					Given an allocation block number, read the bitmap block that
144 					contains that allocation block into a caller-supplied buffer.
163 					allocation file lock must be held.
170 					Test to see if the allocation red-black tree is live.  This function
171 					requires either an exclusive or shared lock on the allocation bitmap file
176 					Multiplexes between the metadata zone trees and the normal allocation zone trees
186 					Exhaustive search function that will check every allocation block for its status in the
205 					Given a starting allocation block number, figures out which physical block contains that
206 					allocation block's bit, and scans it from the starting bit until either the ending bit or
242  * Use sysctl vfs.generic.hfs.kdebug.allocation to control which
252 SYSCTL_INT(_vfs_generic_hfs_kdebug, OID_AUTO, allocation, CTLFLAG_RW|CTLFLAG_LOCKED, &hfs_kdebug_allocation, 0, "Enable kdebug logging for HFS allocations");
257 	 * routines so we can see how an allocation was satisfied.
488  ; Function:		Make note of a range of allocation blocks that should be
499  ;	hfsmp			- The volume containing the allocation blocks.
500  ;	startingBlock	- The first allocation block of the extent being freed.
501  ;	numBlocks		- The number of allocation blocks of the extent being freed.
550  ; Function:	Make note of a range of allocation blocks that should be
562  ;              at mount time, and assumes that there is no allocation/deallocation
566  ;	hfsmp			- The volume containing the allocation blocks.
567  ;	offset          - The first allocation block of the extent being freed.
568  ;	numBlocks		- The number of allocation blocks of the extent being freed.
604  ;	hfsmp			- The volume containing the allocation blocks.
634  ; Function:		Make note of a range of allocation blocks, some of
640  ;	hfsmp			- The volume containing the allocation blocks.
641  ;	startingBlock	- The first allocation block of the extent being allocated.
642  ;	numBlocks		- The number of allocation blocks being allocated.
708 		/* Convert the byte range in *extents back to a range of allocation blocks. */
729  ;	hfsmp			- The volume containing the allocation blocks.
782  ; Function:   Allocate space on a volume.	If contiguous allocation is requested,
784  ;			   error will be returned.	If contiguous allocation is not forced,
786  ;			   at the requested starting allocation block.  If there is not enough
787  ;			   room there, a block allocation of less than the requested size will be
791  ;			   the volume's allocation block pointer will be used as a starting
797  ;	 startingBlock	 - Preferred starting allocation block, 0 = no preference
798  ;	 minBlocks	 	 - Number of blocks requested.	If the allocation is non-contiguous,
808  ;	 (result)		 - Error code, zero for successful allocation
809  ;	 *startBlock	 - Actual starting allocation block
810  ;	 *actualBlocks	 - Actual number of allocation blocks allocated
822 	u_int32_t		*actualStartBlock,	/* actual first block of allocation */
854 	 * TODO: Update BlockAllocate and its sub-functions to do cooperative allocation and bitmap scanning
856 	 * an allocation block of appropriate size, then start scanning blocks FOR the tree generation function until
876 	 * means that we have reserved allocation blocks required for relocating
936 		 * This will keep the roving allocation pointer up-to-date even
982 				// fall through to the normal allocation since the rb-tree allocation failed.
992 		 * contiguous allocation first.
1005 			 * allocation limit.
1030 		//	If we used the volume's roving allocation pointer, then we need to update it.
1031 		//	Adding in the length of the current allocation might reduce the next allocate
1034 		//	the file is closed or its EOF changed.  Leaving the allocation pointer at the
1035 		//	start of the last allocation will avoid unnecessary fragmentation in this case.
1104 ; Function:    Update the bitmap to deallocate a run of disk allocation blocks
1108 ;	 firstBlock	- First allocation block to be freed
1109 ;	 numBlocks	- Number of allocation blocks to free up (must be > 0!)
1299  * Obtain the next allocation block (bit) that's
1300  * outside the metadata allocation zone.
1311 	 * Skip over metadata allocation zone.
1326 ; Function:	Read in a bitmap block corresponding to a given allocation
1354 	 * volume bitmap blocks are protected by the allocation file lock
1362 		vp = vcb->hfs_allocation_vp;	/* use allocation file vnode */
1471 Function:	Allocate a contiguous group of allocation blocks.  The
1472 			allocation is all-or-nothing.  The caller guarantees that
1478 	startingBlock	Preferred first block for allocation
1599 	 * Find the first available extent that satifies the allocation by searching
1649 	 * appropriate free extents, searching by size in the normal allocation zone.
1668 		 * Otherwise, start from the end of the metadata zone or our next allocation pointer,
1768 				panic("hfs: BlockAllocateAny: allocation overflow on \"%s\"", vcb->vcbVN);
1788 Function:	Allocate one or more allocation blocks.  If there are fewer
1795 	startingBlock	Preferred first block for allocation
1833  * BlockAllocateAnyRBTree finds one or more allocation blocks by using
1834  * the red-black allocation tree to figure out where the free ranges are.
1861  * where the free allocation blocks are.  Inputs and outputs are the same as for
2038 						goto Exit;  /* allocation gap, so stop */
2065 			panic("hfs: BlockAllocateAny: allocation overflow on \"%s\"", vcb->vcbVN);
2159 		printf ("hfs: BlockAllocateKnown() found allocation overflow on \"%s\"", vcb->vcbVN);
2279 	//	Pre-read the bitmap block containing the first word of allocation
2314 			numBits = numBlocks;					//	entire allocation is inside this one word
2596 	 * First clear any non bitmap allocation block aligned bits
2712 	//	Pre-read the bitmap block containing the first word of allocation
2765 			numBits = numBlocks;					//	entire allocation is inside this one word
3021 	useMetaZone	OK to dip into metadata allocation zone
3245 						goto LoopExit;  /* allocation gap, so stop */
3320 			panic("hfs: blk allocation overflow on \"%s\" sb:0x%08x eb:0x%08x cb:0x%08x fb:0x%08x stop:0x%08x min:0x%08x found:0x%08x",
3410  * Exhaustive validation search.  This function iterates over all allocation blocks and
3411  * compares their status in the red-black tree vs. the allocation bitmap.  If the two are out of sync
3414  * Because this function requires a red-black tree search to validate every allocation block, it is
3564  * 	startingBlock	First allocation block number of the range to be scanned.
3569  * 	allocCount	Total number of allocation blocks allocated in the given range.
3601 	 * Pre-read the bitmap block containing the first word of allocation
3722  * The journal or allocation file lock must be held.
3745  * The journal or allocation file lock must be held.
3810  * does not have enough extents to satisfy an allocation request.
3812  * startbit		- the allocation block represented by a bit in 'allocblock' where we need to
3813  *				start our scan.  For instance, we may need to start the normal allocation scan
3814  *				in the middle of an existing allocation block.
3815  * endBit		- the allocation block where we should end this search (inclusive).
3955 		 * Pre-read the bitmap block containing the first word of allocation
4025  * after every allocation block that we're working on if an unmount or some other
4049 	 * This loop advances over all allocation bitmap blocks of the current region
4052 	 * because we can release the allocation bitmap lock and allow a thread that wants
4053 	 * to make an allocation to grab the lock and do some scanning on our behalf while we're
4055 	 * scanning as needed to fulfill its allocation.
4067 		 * update our endBlock to match the current allocation limit in the hfsmp struct.
4085 		 * allocation bitmap lock for the entire duration of the tree scan.  For a first check-in
4093 		 *		unlock allocation bitmap lock, fail out.
4183  * or grow the total number of allocation blocks via hfs_truncatefs or hfs_extendfs.
4190  * a re-scan of the new allocation blocks from our current allocLimit to the new end block.
4192  * new_end_block represents the total number of blocks available for allocation in the resized
4228 		 * Find the first available extent that satifies the allocation by searching
4621 	 * casing will need to be done on the allocation side, where we may favor free extents