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.
256  * FUNCTION:	terminate the block allocation map in preparation for
345  *		allocation map.
434  * FUNCTION:	update the allocation state (free or allocate) of the
435  *		specified block range in the persistent block allocation map.
611  * FUNCTION:	find the preferred allocation group for new allocations.
613  *		Within the allocation groups, we maintain a preferred
614  *		allocation group which consists of a group with at least
616  *		new inode allocation towards.  The tie-in between inode
617  *		allocation and block allocation occurs as we allocate the
619  *		as the allocation hint for this block.
622  *		an allocation group, as this will lead to fragmentation.
630  *	the preferred allocation group number.
695  *		blocks from the working allocation block map.
697  *		the block allocation policy uses hints and a multi-step
700  *		for allocation requests smaller than the number of blocks
707  *		if no blocks are available in the dmap or the allocation
709  *		within the same allocation group as contains the hint. if
714  *		for allocation requests larger than the allocation group
719  *	hint	- allocation hint.
761 	 * allocation group size, try to allocate anywhere.  in dbAlloc()
772 	 * If no hint, let dbNextAG recommend an allocation group  in dbAlloc()
788 	/* check if blkno crosses over into a new allocation group.  in dbAlloc()
790 	 * allocation group.  in dbAlloc()
800 	/* check if the allocation request size can be satisfied from a  in dbAlloc()
817 		/* first, try to satisfy the allocation request with the  in dbAlloc()
835 			 * Someone else is writing in this allocation  in dbAlloc()
843 		/* next, try to satisfy the allocation request with blocks  in dbAlloc()
856 		/* try to satisfy the allocation request with blocks within  in dbAlloc()
872 	/* try to satisfy the allocation request with blocks within  in dbAlloc()
873 	 * the same allocation group as the hint.  in dbAlloc()
884 	 * Let dbNextAG recommend a preferred allocation group  in dbAlloc()
889 	/* Try to allocate within this allocation group.  if that fails, try to  in dbAlloc()
909  * FUNCTION:	attempt to extend a current allocation by a specified
912  *		this routine attempts to satisfy the allocation request
913  *		by first trying to extend the existing allocation in
915  *		immediately following the current allocation.  if these
918  *		to cover the existing allocation plus the additional
922  *	ip	    -  pointer to in-core inode requiring allocation.
923  *	blkno	    -  starting block of the current allocation.
925  *		       allocation.
926  *	addnblocks  -  number of blocks to add to the allocation.
928  *		       of the existing allocation if the existing allocation
930  *		       range if the existing allocation could not be extended
944 	/* try to extend the allocation in place.  in dbReAlloc()
954 	/* could not extend the allocation in place, so allocate a  in dbReAlloc()
957 	 * existing allocation plus the additional blocks.)  in dbReAlloc()
967  * FUNCTION:	attempt to extend a current allocation by a specified
970  *		this routine attempts to satisfy the allocation request
971  *		by first trying to extend the existing allocation in
973  *		immediately following the current allocation.
976  *	ip	    -  pointer to in-core inode requiring allocation.
977  *	blkno	    -  starting block of the current allocation.
979  *		       allocation.
980  *	addnblocks  -  number of blocks to add to the allocation.
1005 	/* get the last block of the current allocation */  in dbExtend()
1009 	 * the existing allocation.  in dbExtend()
1023 	/* we'll attempt to extend the current allocation in place by  in dbExtend()
1025 	 * following the current allocation.  we only try to extend the  in dbExtend()
1026 	 * current allocation in place if the number of additional blocks  in dbExtend()
1027 	 * can fit into a dmap, the last block of the current allocation  in dbExtend()
1029 	 * inplace extension is not on an allocation group boundary.  in dbExtend()
1050 	 * current allocation.  in dbExtend()
1276  *		free blocks within the specified allocation group.
1278  *		unless the allocation group size is equal to the number
1282  *		distinctly describes the allocation group's free space
1283  *		(i.e. the highest level at which the allocation group's
1287  *		describe the allocation group's free space.  at this height,
1288  *		the allocation group's free space may be represented by 1
1289  *		or two sub-trees, depending on the allocation group size.
1299  *		if the allocation group size is equal to the dmap size,
1300  *		we'll start at the dmap corresponding to the allocation
1301  *		group and attempt the allocation at this level.
1304  *		allocation group is completely free and we go to the first
1305  *		dmap of the allocation group to do the allocation.  this is
1306  *		done because the allocation group may be part (not the first
1309  *		the allocation group.
1313  *	agno	- allocation group number.
1335 	/* allocation request should not be for more than the  in dbAllocAG()
1336 	 * allocation group size.  in dbAllocAG()
1340 			  "allocation request is larger than the allocation group size\n");  in dbAllocAG()
1344 	/* determine the starting block number of the allocation  in dbAllocAG()
1349 	/* check if the allocation group size is the minimum allocation  in dbAllocAG()
1350 	 * group size or if the allocation group is completely free. if  in dbAllocAG()
1351 	 * the allocation group size is the minimum size of BPERDMAP (i.e.  in dbAllocAG()
1353 	 * that fully describes the allocation group since the allocation  in dbAllocAG()
1358 	 * if the allocation group is completely free, dbAllocCtl() is  in dbAllocAG()
1362 	 * the dmap control pages may indicate that the allocation group  in dbAllocAG()
1363 	 * has no free space if the allocation group is part (not the first  in dbAllocAG()
1381 	 * allocation group.  in dbAllocAG()
1397 	 * the allocation group, looking for sufficient free space.  to begin,  in dbAllocAG()
1398 	 * determine how many allocation groups are represented in a dmap  in dbAllocAG()
1400 	 * fully describes an allocation group. next, determine the starting  in dbAllocAG()
1401 	 * tree index of this allocation group within the control page.  in dbAllocAG()
1407 	/* dmap control page trees fan-out by 4 and a single allocation  in dbAllocAG()
1490 	/* no space in the allocation group.  release the buffer and  in dbAllocAG()
1667  *		contiguous free blocks large enough to satisfy an allocation
1780  *		specifically, this occurs when allocating from an allocation
1796  *	blkno	 -  starting block number of the dmap to start the allocation
1816 	/* check if the allocation request is confined to a single dmap.  in dbAllocCtl()
1841 	/* allocation request involving multiple dmaps. it must start on  in dbAllocCtl()
1890 	/* something failed in handling an allocation request involving  in dbAllocCtl()
1892 	 * allocation that has already happened for this request.  if  in dbAllocCtl()
1893 	 * we fail in backing out the allocation, we'll mark the file  in dbAllocCtl()
2005  * FUNCTION:	adjust the disk allocation map to reflect the allocation
2009  *		through a call to dbAllocBits(). if the allocation of the
2049 	 * backout the bit allocation (thus making everything consistent).  in dbAllocDmap()
2061  * FUNCTION:	adjust the disk allocation map to reflect the allocation
2130  *		state allocation of the specified block range. it directly
2235 				/* update the leaf to reflect the allocation.  in dbAllocBits()
2239 				 * allocation (size).  in dbAllocBits()
2255 	/* if this allocation group is completely free,  in dbAllocBits()
2256 	 * update the maximum allocation group number if this allocation  in dbAllocBits()
2263 	/* update the free count for the allocation group and map */  in dbAllocBits()
2277  *		state allocation of the specified block range. it directly
2399 	/* update the free count for the allocation group and  in dbFreeBits()
2406 	/* check if this allocation group is not completely free and  in dbFreeBits()
2407 	 * if it is currently the maximum (rightmost) allocation group.  in dbFreeBits()
2408 	 * if so, establish the new maximum allocation group number by  in dbFreeBits()
2409 	 * searching left for the first allocation group with allocation.  in dbFreeBits()
2421 		/* re-establish the allocation group preference if the  in dbFreeBits()
2422 		 * current preference is right of the maximum allocation  in dbFreeBits()
2441  *		of the lower level object's dmtree) due to the allocation
2446  *		starting block number of the block range whose allocation
2462  *		   the allocation or deallocation of this block range that
2466  *	alloc	-  'true' if adjustment is due to an allocation.
2513 	/* check if this is a control page update for an allocation.  in dbAdjCtl()
2526 		 * first allocation out of an allocation group that  in dbAdjCtl()
2680  *		any required splits.  in some cases, however, allocation
2685  *		is required are rare and are limited to the first allocation
2686  *		within an allocation group which is a part (not first part)
3184  *		allocation map.
3328 	/* if this allocation group is completely free,  in dbAllocDmapBU()
3329 	 * update the highest active allocation group number  in dbAllocDmapBU()
3330 	 * if this allocation group is the new max.  in dbAllocDmapBU()
3336 	/* update the free count for the allocation group and map */  in dbAllocDmapBU()
3348 	 * backout the bit allocation (thus making everything consistent).  in dbAllocDmapBU()
3667 	/* determine how many blocks are in the inactive allocation  in dbFinalizeBmap()
3677 	 * allocation groups plus the average number of free blocks  in dbFinalizeBmap()
3683 	/* if the preferred allocation group has not average free space.  in dbFinalizeBmap()
3987  * FUNCTION:	Determine log2(allocation group size) from aggregate size
3992  * RETURNS: log2(allocation group size) in aggregate blocks
4022  * FUNCTION:	compute number of blocks the block allocation map file