19  *	SERIALIZATION of the Block Allocation Map.
21  *	the working state of the block allocation map is accessed in
24  *	1) allocation and free requests that start at the dmap
28  *	2) allocation requests that start at dmap control page
46  *	the working state of the block allocation map also includes read/
48  *	free block count, allocation group level free block counts).
53  *	accesses to the persistent state of the block allocation map (limited
139  * FUNCTION:	initializate the block allocation map.
216  * FUNCTION:	terminate the block allocation map in preparation for
304  *		allocation map.
392  * FUNCTION:	update the allocation state (free or allocate) of the
393  *		specified block range in the persistent block allocation map.
569  * FUNCTION:	find the preferred allocation group for new allocations.
571  *		Within the allocation groups, we maintain a preferred
572  *		allocation group which consists of a group with at least
574  *		new inode allocation towards.  The tie-in between inode
575  *		allocation and block allocation occurs as we allocate the
577  *		as the allocation hint for this block.
580  *		an allocation group, as this will lead to fragmentation.
588  *	the preferred allocation group number.
653  *		blocks from the working allocation block map.
655  *		the block allocation policy uses hints and a multi-step
658  *		for allocation requests smaller than the number of blocks
665  *		if no blocks are available in the dmap or the allocation
667  *		within the same allocation group as contains the hint. if
672  *		for allocation requests larger than the allocation group
677  *	hint	- allocation hint.
719 	 * allocation group size, try to allocate anywhere.  in dbAlloc()
730 	 * If no hint, let dbNextAG recommend an allocation group  in dbAlloc()
746 	/* check if blkno crosses over into a new allocation group.  in dbAlloc()
748 	 * allocation group.  in dbAlloc()
758 	/* check if the allocation request size can be satisfied from a  in dbAlloc()
775 		/* first, try to satisfy the allocation request with the  in dbAlloc()
793 			 * Someone else is writing in this allocation  in dbAlloc()
801 		/* next, try to satisfy the allocation request with blocks  in dbAlloc()
814 		/* try to satisfy the allocation request with blocks within  in dbAlloc()
830 	/* try to satisfy the allocation request with blocks within  in dbAlloc()
831 	 * the same allocation group as the hint.  in dbAlloc()
842 	 * Let dbNextAG recommend a preferred allocation group  in dbAlloc()
847 	/* Try to allocate within this allocation group.  if that fails, try to  in dbAlloc()
896 	 *  allocation request size must be satisfied from a single dmap.  in dbAllocExact()
935  * FUNCTION:	attempt to extend a current allocation by a specified
938  *		this routine attempts to satisfy the allocation request
939  *		by first trying to extend the existing allocation in
941  *		immediately following the current allocation.  if these
944  *		to cover the existing allocation plus the additional
948  *	ip	    -  pointer to in-core inode requiring allocation.
949  *	blkno	    -  starting block of the current allocation.
951  *		       allocation.
952  *	addnblocks  -  number of blocks to add to the allocation.
954  *		       of the existing allocation if the existing allocation
956  *		       range if the existing allocation could not be extended
970 	/* try to extend the allocation in place.  in dbReAlloc()
980 	/* could not extend the allocation in place, so allocate a  in dbReAlloc()
983 	 * existing allocation plus the additional blocks.)  in dbReAlloc()
993  * FUNCTION:	attempt to extend a current allocation by a specified
996  *		this routine attempts to satisfy the allocation request
997  *		by first trying to extend the existing allocation in
999  *		immediately following the current allocation.
1002  *	ip	    -  pointer to in-core inode requiring allocation.
1003  *	blkno	    -  starting block of the current allocation.
1005  *		       allocation.
1006  *	addnblocks  -  number of blocks to add to the allocation.
1031 	/* get the last block of the current allocation */  in dbExtend()
1035 	 * the existing allocation.  in dbExtend()
1049 	/* we'll attempt to extend the current allocation in place by  in dbExtend()
1051 	 * following the current allocation.  we only try to extend the  in dbExtend()
1052 	 * current allocation in place if the number of additional blocks  in dbExtend()
1053 	 * can fit into a dmap, the last block of the current allocation  in dbExtend()
1055 	 * inplace extension is not on an allocation group boundary.  in dbExtend()
1076 	 * current allocation.  in dbExtend()
1302  *		free blocks within the specified allocation group.
1304  *		unless the allocation group size is equal to the number
1308  *		distinctly describes the allocation group's free space
1309  *		(i.e. the highest level at which the allocation group's
1313  *		describe the allocation group's free space.  at this height,
1314  *		the allocation group's free space may be represented by 1
1315  *		or two sub-trees, depending on the allocation group size.
1325  *		if the allocation group size is equal to the dmap size,
1326  *		we'll start at the dmap corresponding to the allocation
1327  *		group and attempt the allocation at this level.
1330  *		allocation group is completely free and we go to the first
1331  *		dmap of the allocation group to do the allocation.  this is
1332  *		done because the allocation group may be part (not the first
1335  *		the allocation group.
1339  *	agno	- allocation group number.
1361 	/* allocation request should not be for more than the  in dbAllocAG()
1362 	 * allocation group size.  in dbAllocAG()
1366 			  "allocation request is larger than the allocation group size\n");  in dbAllocAG()
1370 	/* determine the starting block number of the allocation  in dbAllocAG()
1375 	/* check if the allocation group size is the minimum allocation  in dbAllocAG()
1376 	 * group size or if the allocation group is completely free. if  in dbAllocAG()
1377 	 * the allocation group size is the minimum size of BPERDMAP (i.e.  in dbAllocAG()
1379 	 * that fully describes the allocation group since the allocation  in dbAllocAG()
1384 	 * if the allocation group is completely free, dbAllocCtl() is  in dbAllocAG()
1388 	 * the dmap control pages may indicate that the allocation group  in dbAllocAG()
1389 	 * has no free space if the allocation group is part (not the first  in dbAllocAG()
1407 	 * allocation group.  in dbAllocAG()
1423 	 * the allocation group, looking for sufficient free space.  to begin,  in dbAllocAG()
1424 	 * determine how many allocation groups are represented in a dmap  in dbAllocAG()
1426 	 * fully describes an allocation group. next, determine the starting  in dbAllocAG()
1427 	 * tree index of this allocation group within the control page.  in dbAllocAG()
1433 	/* dmap control page trees fan-out by 4 and a single allocation  in dbAllocAG()
1516 	/* no space in the allocation group.  release the buffer and  in dbAllocAG()
1691  *		contiguous free blocks large enough to satisfy an allocation
1804  *		specifically, this occurs when allocating from an allocation
1820  *	blkno	 -  starting block number of the dmap to start the allocation
1840 	/* check if the allocation request is confined to a single dmap.  in dbAllocCtl()
1862 	/* allocation request involving multiple dmaps. it must start on  in dbAllocCtl()
1911 	/* something failed in handling an allocation request involving  in dbAllocCtl()
1913 	 * allocation that has already happened for this request.  if  in dbAllocCtl()
1914 	 * we fail in backing out the allocation, we'll mark the file  in dbAllocCtl()
2023  * FUNCTION:	adjust the disk allocation map to reflect the allocation
2027  *		through a call to dbAllocBits(). if the allocation of the
2067 	 * backout the bit allocation (thus making everything consistent).  in dbAllocDmap()
2079  * FUNCTION:	adjust the disk allocation map to reflect the allocation
2148  *		state allocation of the specified block range. it directly
2253 				/* update the leaf to reflect the allocation.  in dbAllocBits()
2257 				 * allocation (size).  in dbAllocBits()
2273 	/* if this allocation group is completely free,  in dbAllocBits()
2274 	 * update the maximum allocation group number if this allocation  in dbAllocBits()
2281 	/* update the free count for the allocation group and map */  in dbAllocBits()
2295  *		state allocation of the specified block range. it directly
2417 	/* update the free count for the allocation group and  in dbFreeBits()
2424 	/* check if this allocation group is not completely free and  in dbFreeBits()
2425 	 * if it is currently the maximum (rightmost) allocation group.  in dbFreeBits()
2426 	 * if so, establish the new maximum allocation group number by  in dbFreeBits()
2427 	 * searching left for the first allocation group with allocation.  in dbFreeBits()
2439 		/* re-establish the allocation group preference if the  in dbFreeBits()
2440 		 * current preference is right of the maximum allocation  in dbFreeBits()
2459  *		of the lower level object's dmtree) due to the allocation
2464  *		starting block number of the block range whose allocation
2480  *		   the allocation or deallocation of this block range that
2484  *	alloc	-  'true' if adjustment is due to an allocation.
2531 	/* check if this is a control page update for an allocation.  in dbAdjCtl()
2544 		 * first allocation out of an allocation group that  in dbAdjCtl()
2694  *		any required splits.  in some cases, however, allocation
2699  *		is required are rare and are limited to the first allocation
2700  *		within an allocation group which is a part (not first part)
3181  *		allocation map.
3325 	/* if this allocation group is completely free,  in dbAllocDmapBU()
3326 	 * update the highest active allocation group number  in dbAllocDmapBU()
3327 	 * if this allocation group is the new max.  in dbAllocDmapBU()
3333 	/* update the free count for the allocation group and map */  in dbAllocDmapBU()
3345 	 * backout the bit allocation (thus making everything consistent).  in dbAllocDmapBU()
3664 	/* determine how many blocks are in the inactive allocation  in dbFinalizeBmap()
3674 	 * allocation groups plus the average number of free blocks  in dbFinalizeBmap()
3680 	/* if the preferred allocation group has not average free space.  in dbFinalizeBmap()
3984  * FUNCTION:	Determine log2(allocation group size) from aggregate size
3989  * RETURNS: log2(allocation group size) in aggregate blocks
4019  * FUNCTION:	compute number of blocks the block allocation map file