hfscommon/Misc/VolumeAllocation.c

44 					asked for.  Returns the starting block number, and number of
102 					specifies where to begin the search (by block number).  The
103 					block number of the first block in the range is returned.  This is only
143 					Given an allocation block number, read the bitmap block that
144 					contains that allocation block into a caller-supplied buffer.
147 					Release a bitmap block back into the buffer cache.
167 					invalidates the block used when finished.
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
207 					the end of the block.  Free space extents are inserted into the appropriate red-black tree.
500  ;	startingBlock	- The first allocation block of the extent being freed.
567  ;	offset          - The first allocation block of the extent being freed.
641  ;	startingBlock	- The first allocation block of the extent being allocated.
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
790  ;			   If the requested starting block is 0 (for new file allocations),
791  ;			   the volume's allocation block pointer will be used as a starting
797  ;	 startingBlock	 - Preferred starting allocation block, 0 = no preference
805  ;					   skip free block check, etc.
809  ;	 *startBlock	 - Actual starting allocation block
818 	u_int32_t		startingBlock,		/* preferred starting block, or 0 for no preference */
822 	u_int32_t		*actualStartBlock,	/* actual first block of allocation */
856 	 * an allocation block of appropriate size, then start scanning blocks FOR the tree generation function until
870 	/* Skip free block check if blocks are being allocated for relocating
873 	 * During hfs_truncatefs(), the volume free block count is updated
905 	//	If caller didn't specify a starting block number, then use the volume's
906 	//	next block to allocate from.
929 	//	that is long enough.  Otherwise, find the first free block.
939 		 * the block to vend out.
955 			/* Start by trying to allocate from the starting block forward */
1013 			 * We may be out of space in the normal zone; go up to the starting block from
1026 	// still need to update things like the free block count).
1061 		 * Skip updating the free blocks count if the block are
1079 				panic ("BlockAllocate: vending block past allocLimit!");
1108 ;	 firstBlock	- First allocation block to be freed
1122 	u_int32_t		firstBlock,		//	First block in range to deallocate
1163 	 * building.  In that case, check to see if the block we're de-allocating is
1189 	//	Update the volume's free block count, and mark the VCB as dirty.
1194 	 * Do not update the free block count.  This flags is specified
1272 		 *  Get next bitmap block.
1299  * Obtain the next allocation block (bit) that's
1326 ; Function:	Read in a bitmap block corresponding to a given allocation
1327 ;			block (bit).  Return a pointer to the bitmap block.
1331 ;	bit			--	Allocation block whose bitmap block is desired
1334 ;	buffer		--	Pointer to bitmap block corresonding to "block"
1347 	daddr64_t block;
1359 	block = (daddr64_t)(bit / (blockSize * kBitsPerByte));
1366 		block += vcb->vcbVBMSt;			/* map to physical block */
1369 	err = (int)buf_meta_bread(vp, block, blockSize, NOCRED, &bp);
1394 ; Function:	Relase a bitmap block.
1478 	startingBlock	Preferred first block for allocation
1484 	actualStartBlock	First block of range allocated, or 0 if error
1657 	 * which the minimum block size is 1 block, making it easy to succeed.
1791 			one free block.
1795 	startingBlock	Preferred first block for allocation
1796 	endingBlock		Last block to check + 1
1801 	actualStartBlock	First block of range allocated, or 0 if error
1875 	register u_int32_t	block;			//	current block number
1876 	register u_int32_t	currentWord;	//	Pointer to current word within bitmap block
1878 	register u_int32_t	wordsLeft;		//	Number of words left in this bitmap block
1914 	//	Pre-read the first bitmap block
1921 	//	Set up the current position within the block
1937 	//	Find the first unallocated block
1939 	block=startingBlock;
1940 	while (block < endingBlock) {
1945 		++block;
1953 				//	Next block
1962 					block = NextBitmapBlock(vcb, block);
1964 				if (block >= endingBlock) {
1969 				err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
1979 	//	Did we get to the end of the bitmap before finding a free block?
1981 	if (block >= endingBlock) {
1986 	//	Return the first block in the allocated range
1987 	*actualStartBlock = block;
1992 	//	would be (block + maxBlocks) < endingBlock, but that could overflow.  The
1994 	if (block < (endingBlock-maxBlocks)) {
1995 		endingBlock = block + maxBlocks;	//	if we get this far, we've found enough
2007 		//	Allocate this block
2010 		//	Move to the next block.  If no more, then exit.
2011 		++block;
2012 		if (block == endingBlock)
2025 				//	Next block
2036 					nextBlock = NextBitmapBlock(vcb, block);
2037 					if (nextBlock != block) {
2042 				err = ReadBitmapBlock(vcb, block, &currCache, &blockRef);
2061 		*actualNumBlocks = block - *actualStartBlock;
2109 	actualStartBlock	First block of range allocated, or 0 if error
2250 	startingBlock	First block number to mark as allocated
2261 	register u_int32_t	*currentWord;	//	Pointer to current word within bitmap block
2262 	register u_int32_t	wordsLeft;		//	Number of words left in this bitmap block
2279 	//	Pre-read the bitmap block containing the first word of allocation
2304 	//	If the first block to allocate doesn't start on a word
2326 		--wordsLeft;								//	one less word left in this block
2336 			//	Read in the next bitmap block
2337 			startingBlock += bitsPerBlock;			//	generate a block number in the next bitmap block
2364 		--wordsLeft;								//	one less word left in this block
2374 			//	Read in the next bitmap block
2375 			startingBlock += bitsPerBlock;				//	generate a block number in the next bitmap block
2417  * called when the RB Tree-based allocator needs to mark a block as in-use.
2563  * Scan the bitmap block beyond end of current file system for bits
2579  * 	startingBlock: First block of the range to mark unused
2592 	/* Use the optimal bitmap I/O size instead of bitmap block size */
2596 	 * First clear any non bitmap allocation block aligned bits
2598 	 * Calculate the first bit in the bitmap block next to
2599 	 * the bitmap block containing the bit for startingBlock.
2602 	 * end of bitmap block containing startingBlock.
2617 	 * Check a full bitmap block for any 'used' bit.  If any bit is used,
2618 	 * mark all the bits only in that bitmap block as free.  This ensures
2622 	 * The code starts by checking full bitmap block at a time, and
2623 	 * marks entire bitmap block as free only if any bit in that bitmap
2624 	 * block is marked as used.  In the end, it handles the last bitmap
2625 	 * block which might be partially full by only checking till the
2659 	startingBlock	First block number to mark as freed
2680 	u_int32_t	*currentWord;	//	Pointer to current word within bitmap block
2681 	u_int32_t	wordsLeft;		//	Number of words left in this bitmap block
2712 	//	Pre-read the bitmap block containing the first word of allocation
2723 	//	Figure out how many bits and words per bitmap block.
2731 	// (up to the start of the current bitmap block).  Set unmapStart to
2732 	// the first free block.
2747 			break;	// Found an allocated block.  Stop searching.
2753 	//	If the first block to free doesn't start on a word
2776 		--wordsLeft;								//	one less word left in this block
2785 			//	Read in the next bitmap block
2786 			startingBlock += bitsPerBlock;			//	generate a block number in the next bitmap block
2812 		--wordsLeft;									//	one less word left in this block
2822 			//	Read in the next bitmap block
2823 			startingBlock += bitsPerBlock;				//	generate a block number in the next bitmap block
2852 	// (up to the end of the current bitmap block).
2870 			break;	// Found an allocated block.  Stop searching.
2903  * called when the RB Tree-based allocator needs to mark a block as no longer
3017 	startingBlock	Preferred first block of range
3018 	endingBlock		Last possible block in range + 1
3024 	actualStartBlock	First block of range found, or 0 if error
3045 	u_int32_t			firstBlock;			//	First free block in current extent.
3046 	u_int32_t			stopBlock;			//	If we get to this block, stop searching for first free block.
3094 	//	Pre-read the first bitmap block.
3113 		//	Look for a free block, skipping over allocated blocks.
3144 			//	See if it's time to read another block.
3230 			//	See if it's time to read another block.
3281 		//	Make sure we didn't run out of bitmap looking for a used block.
3295 		 * lets add this free block run to our free extent cache list
3330 		// set the nextAllocation pointer to the smallest free block number
3414  * Because this function requires a red-black tree search to validate every allocation block, it is
3434 			panic("HFS: Allocator mismatch @ block %d -- bitmap %d : rbtree %d\n",
3528 	 * at least one block in the target range is allocated since the next node's offset
3560  * encounters the first allocated block.  This option is useful
3561  * to determine if any block is allocated or not.
3564  * 	startingBlock	First allocation block number of the range to be scanned.
3566  * 	stop_on_first	Stop the search after the first allocated block is found.
3575  * 				allocCount = 1 if any allocated block was found.
3576  * 				allocCount = 0 if no allocated block was found.
3585 	u_int32_t  *currentWord;   // Pointer to current word within bitmap block
3586 	u_int32_t  wordsLeft;      // Number of words left in this bitmap block
3601 	 * Pre-read the bitmap block containing the first word of allocation
3649 			/* Read in the next bitmap block. */
3681 			/* Read in the next bitmap block */
3765 		 * if there was any block allocated or not.  In that case,
3804  * This function scans the specified bitmap block and acts on it as necessary.
3812  * startbit		- the allocation block represented by a bit in 'allocblock' where we need to
3814  *				in the middle of an existing allocation block.
3815  * endBit		- the allocation block where we should end this search (inclusive).
3838 	 * Read the appropriate block from the bitmap file.  ReadBitmapBlock
3839 	 * figures out which actual on-disk block corresponds to the bit we're
3847 	/* curAllocBlock represents the logical block we're analyzing. */
3850 	/*  Figure out which word curAllocBlock corresponds to in the block we read  */
3881 				 * If we hit an allocated block, insert the extent that tracked the range
3914 	 * curAllocBlock represents the next block we need to scan while we're in this
3935 	u_int32_t  *currentWord;   // Pointer to current word within bitmap block
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
4045 	/* Initialize the block counter while we hold the bitmap lock */
4060 	 * block that needs scanning.
4190  * a re-scan of the new allocation blocks from our current allocLimit to the new end block.
4477  *	startBlock	- starting block of the extent to be removed.
4598  *	startBlock	- starting block of the extent to be removed.
4750 				/* sparse devices are sorted by starting block number (ascending) */
4757 				/* normally sorted by block count (descending) */