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.
223  * FUNCTION:	terminate the block allocation map in preparation for
311  *		allocation map.
400  * FUNCTION:	update the allocation state (free or allocate) of the
401  *		specified block range in the persistent block allocation map.
577  * FUNCTION:	find the preferred allocation group for new allocations.
579  *		Within the allocation groups, we maintain a preferred
580  *		allocation group which consists of a group with at least
582  *		new inode allocation towards.  The tie-in between inode
583  *		allocation and block allocation occurs as we allocate the
585  *		as the allocation hint for this block.
588  *		an allocation group, as this will lead to fragmentation.
596  *	the preferred allocation group number.
661  *		blocks from the working allocation block map.
663  *		the block allocation policy uses hints and a multi-step
666  *		for allocation requests smaller than the number of blocks
673  *		if no blocks are available in the dmap or the allocation
675  *		within the same allocation group as contains the hint. if
680  *		for allocation requests larger than the allocation group
685  *	hint	- allocation hint.
727 	 * allocation group size, try to allocate anywhere.  in dbAlloc()
738 	 * If no hint, let dbNextAG recommend an allocation group  in dbAlloc()
754 	/* check if blkno crosses over into a new allocation group.  in dbAlloc()
756 	 * allocation group.  in dbAlloc()
766 	/* check if the allocation request size can be satisfied from a  in dbAlloc()
783 		/* first, try to satisfy the allocation request with the  in dbAlloc()
801 			 * Someone else is writing in this allocation  in dbAlloc()
809 		/* next, try to satisfy the allocation request with blocks  in dbAlloc()
822 		/* try to satisfy the allocation request with blocks within  in dbAlloc()
838 	/* try to satisfy the allocation request with blocks within  in dbAlloc()
839 	 * the same allocation group as the hint.  in dbAlloc()
850 	 * Let dbNextAG recommend a preferred allocation group  in dbAlloc()
855 	/* Try to allocate within this allocation group.  if that fails, try to  in dbAlloc()
875  * FUNCTION:	attempt to extend a current allocation by a specified
878  *		this routine attempts to satisfy the allocation request
879  *		by first trying to extend the existing allocation in
881  *		immediately following the current allocation.  if these
884  *		to cover the existing allocation plus the additional
888  *	ip	    -  pointer to in-core inode requiring allocation.
889  *	blkno	    -  starting block of the current allocation.
891  *		       allocation.
892  *	addnblocks  -  number of blocks to add to the allocation.
894  *		       of the existing allocation if the existing allocation
896  *		       range if the existing allocation could not be extended
910 	/* try to extend the allocation in place.  in dbReAlloc()
920 	/* could not extend the allocation in place, so allocate a  in dbReAlloc()
923 	 * existing allocation plus the additional blocks.)  in dbReAlloc()
933  * FUNCTION:	attempt to extend a current allocation by a specified
936  *		this routine attempts to satisfy the allocation request
937  *		by first trying to extend the existing allocation in
939  *		immediately following the current allocation.
942  *	ip	    -  pointer to in-core inode requiring allocation.
943  *	blkno	    -  starting block of the current allocation.
945  *		       allocation.
946  *	addnblocks  -  number of blocks to add to the allocation.
971 	/* get the last block of the current allocation */  in dbExtend()
975 	 * the existing allocation.  in dbExtend()
989 	/* we'll attempt to extend the current allocation in place by  in dbExtend()
991 	 * following the current allocation.  we only try to extend the  in dbExtend()
992 	 * current allocation in place if the number of additional blocks  in dbExtend()
993 	 * can fit into a dmap, the last block of the current allocation  in dbExtend()
995 	 * inplace extension is not on an allocation group boundary.  in dbExtend()
1016 	 * current allocation.  in dbExtend()
1242  *		free blocks within the specified allocation group.
1244  *		unless the allocation group size is equal to the number
1248  *		distinctly describes the allocation group's free space
1249  *		(i.e. the highest level at which the allocation group's
1253  *		describe the allocation group's free space.  at this height,
1254  *		the allocation group's free space may be represented by 1
1255  *		or two sub-trees, depending on the allocation group size.
1265  *		if the allocation group size is equal to the dmap size,
1266  *		we'll start at the dmap corresponding to the allocation
1267  *		group and attempt the allocation at this level.
1270  *		allocation group is completely free and we go to the first
1271  *		dmap of the allocation group to do the allocation.  this is
1272  *		done because the allocation group may be part (not the first
1275  *		the allocation group.
1279  *	agno	- allocation group number.
1301 	/* allocation request should not be for more than the  in dbAllocAG()
1302 	 * allocation group size.  in dbAllocAG()
1306 			  "allocation request is larger than the allocation group size\n");  in dbAllocAG()
1310 	/* determine the starting block number of the allocation  in dbAllocAG()
1315 	/* check if the allocation group size is the minimum allocation  in dbAllocAG()
1316 	 * group size or if the allocation group is completely free. if  in dbAllocAG()
1317 	 * the allocation group size is the minimum size of BPERDMAP (i.e.  in dbAllocAG()
1319 	 * that fully describes the allocation group since the allocation  in dbAllocAG()
1324 	 * if the allocation group is completely free, dbAllocCtl() is  in dbAllocAG()
1328 	 * the dmap control pages may indicate that the allocation group  in dbAllocAG()
1329 	 * has no free space if the allocation group is part (not the first  in dbAllocAG()
1347 	 * allocation group.  in dbAllocAG()
1363 	 * the allocation group, looking for sufficient free space.  to begin,  in dbAllocAG()
1364 	 * determine how many allocation groups are represented in a dmap  in dbAllocAG()
1366 	 * fully describes an allocation group. next, determine the starting  in dbAllocAG()
1367 	 * tree index of this allocation group within the control page.  in dbAllocAG()
1373 	/* dmap control page trees fan-out by 4 and a single allocation  in dbAllocAG()
1456 	/* no space in the allocation group.  release the buffer and  in dbAllocAG()
1631  *		contiguous free blocks large enough to satisfy an allocation
1744  *		specifically, this occurs when allocating from an allocation
1760  *	blkno	 -  starting block number of the dmap to start the allocation
1780 	/* check if the allocation request is confined to a single dmap.  in dbAllocCtl()
1802 	/* allocation request involving multiple dmaps. it must start on  in dbAllocCtl()
1851 	/* something failed in handling an allocation request involving  in dbAllocCtl()
1853 	 * allocation that has already happened for this request.  if  in dbAllocCtl()
1854 	 * we fail in backing out the allocation, we'll mark the file  in dbAllocCtl()
1963  * FUNCTION:	adjust the disk allocation map to reflect the allocation
1967  *		through a call to dbAllocBits(). if the allocation of the
2007 	 * backout the bit allocation (thus making everything consistent).  in dbAllocDmap()
2019  * FUNCTION:	adjust the disk allocation map to reflect the allocation
2088  *		state allocation of the specified block range. it directly
2193 				/* update the leaf to reflect the allocation.  in dbAllocBits()
2197 				 * allocation (size).  in dbAllocBits()
2213 	/* if this allocation group is completely free,  in dbAllocBits()
2214 	 * update the maximum allocation group number if this allocation  in dbAllocBits()
2221 	/* update the free count for the allocation group and map */  in dbAllocBits()
2235  *		state allocation of the specified block range. it directly
2357 	/* update the free count for the allocation group and  in dbFreeBits()
2364 	/* check if this allocation group is not completely free and  in dbFreeBits()
2365 	 * if it is currently the maximum (rightmost) allocation group.  in dbFreeBits()
2366 	 * if so, establish the new maximum allocation group number by  in dbFreeBits()
2367 	 * searching left for the first allocation group with allocation.  in dbFreeBits()
2379 		/* re-establish the allocation group preference if the  in dbFreeBits()
2380 		 * current preference is right of the maximum allocation  in dbFreeBits()
2399  *		of the lower level object's dmtree) due to the allocation
2404  *		starting block number of the block range whose allocation
2420  *		   the allocation or deallocation of this block range that
2424  *	alloc	-  'true' if adjustment is due to an allocation.
2471 	/* check if this is a control page update for an allocation.  in dbAdjCtl()
2484 		 * first allocation out of an allocation group that  in dbAdjCtl()
2638  *		any required splits.  in some cases, however, allocation
2643  *		is required are rare and are limited to the first allocation
2644  *		within an allocation group which is a part (not first part)
3125  *		allocation map.
3269 	/* if this allocation group is completely free,  in dbAllocDmapBU()
3270 	 * update the highest active allocation group number  in dbAllocDmapBU()
3271 	 * if this allocation group is the new max.  in dbAllocDmapBU()
3277 	/* update the free count for the allocation group and map */  in dbAllocDmapBU()
3289 	 * backout the bit allocation (thus making everything consistent).  in dbAllocDmapBU()
3608 	/* determine how many blocks are in the inactive allocation  in dbFinalizeBmap()
3618 	 * allocation groups plus the average number of free blocks  in dbFinalizeBmap()
3624 	/* if the preferred allocation group has not average free space.  in dbFinalizeBmap()
3928  * FUNCTION:	Determine log2(allocation group size) from aggregate size
3933  * RETURNS: log2(allocation group size) in aggregate blocks
3963  * FUNCTION:	compute number of blocks the block allocation map file