24  *	1) allocation and free requests that start at the dmap
48  *	free block count, allocation group level free block counts).
115  * binary buddy of free bits within the character.
241 	/* free the memory for the in-memory bmap. */  in dbUnmount()
303  * FUNCTION:	free the specified block range from the working block
306  *		the blocks will be free from the working map one dmap
348 	 * free the blocks a dmap at a time.  in dbFree()
371 		/* free the blocks. */  in dbFree()
392  * FUNCTION:	update the allocation state (free or allocate) of the
400  *	free	- 'true' if block range is to be freed from the persistent
412 	     int free, s64 blkno, s64 nblocks, struct tblock * tblk)  in dbUpdatePMap()  argument
485 				/* update (free or allocate) the bits  in dbUpdatePMap()
490 				if (free)  in dbUpdatePMap()
506 				/* update (free or allocate) the bits  in dbUpdatePMap()
509 				if (free)  in dbUpdatePMap()
573  *		average free space.  It is the preferred group that we target
601 	/* determine the average number of free blocks within the ags. */  in dbNextAG()
614 	 * average free space.  in dbNextAG()
652  * FUNCTION:	attempt to allocate a specified number of contiguous free
737 	 * will start looking for free space starting at this point.  in dbAlloc()
753 		 * AG with sufficient free space.  in dbAlloc()
904 		/* the free space is no longer available */  in dbAllocExact()
1103  *	nblocks	-  number of contiguous free blocks of the range.
1142 	 * is free.  in dbAllocNext()
1148 	 * if the block range is free.  not all bits of the first and  in dbAllocNext()
1152 	 * the actual bits to determine if they are free.  a single pass  in dbAllocNext()
1155 	 * tree will be examined to determine if the blocks are free. a  in dbAllocNext()
1156 	 * single leaf may describe the free space of multiple dmap  in dbAllocNext()
1170 			/* check if the bits are free.  in dbAllocNext()
1186 			 * if the blocks are free.  in dbAllocNext()
1189 				/* does the leaf describe any free space ?  in dbAllocNext()
1219  * FUNCTION:	attempt to allocate a number of contiguous free blocks near
1223  *		check the next four contiguous leaves for sufficient free
1224  *		space.  if sufficient free space is found, we'll allocate
1225  *		the desired free space.
1231  *	nblocks	-  actual number of contiguous free blocks desired.
1232  *	l2nb	-  log2 number of contiguous free blocks desired.
1264 	/* examine the leaves for sufficient free space.  in dbAllocNear()
1267 		/* does the leaf describe sufficient free space ?  in dbAllocNear()
1277 		/* if not all bits of the dmap word are free, get the  in dbAllocNear()
1279 		 * string of free bits and adjust the block number with the  in dbAllocNear()
1302  *		free blocks within the specified allocation group.
1306  *		find the required free space, if available.  we start the
1308  *		distinctly describes the allocation group's free space
1310  *		free space is not mixed in with that of any other group).
1313  *		describe the allocation group's free space.  at this height,
1314  *		the allocation group's free space may be represented by 1
1317  *		sufficient free space.  if sufficient free space is found,
1319  *		has free space.  once we have made it to the leaf, we
1323  *		sufficient free space and we allocate at this dmap.
1330  *		allocation group is completely free and we go to the first
1334  *		control pages to indicate no free space (NOFREE) within
1340  *	nblocks	-  actual number of contiguous free blocks desired.
1341  *	l2nb	-  log2 number of contiguous free blocks desired.
1376 	 * group size or if the allocation group is completely free. if  in dbAllocAG()
1384 	 * if the allocation group is completely free, dbAllocCtl() is  in dbAllocAG()
1387 	 * pages for free space when we know that free space exists.  second,  in dbAllocAG()
1389 	 * has no free space if the allocation group is part (not the first  in dbAllocAG()
1401 				  "dbAllocCtl failed in free AG\n");  in dbAllocAG()
1423 	 * the allocation group, looking for sufficient free space.  to begin,  in dbAllocAG()
1436 	 * subtrees for sufficient free space, starting with the leftmost  in dbAllocAG()
1440 		/* is there sufficient free space ?  in dbAllocAG()
1445 		/* sufficient free space found in a subtree. now search down  in dbAllocAG()
1447 		 * free space.  in dbAllocAG()
1491 			 * contains or starts off the free space.  in dbAllocAG()
1529  *		free blocks anywhere in the file system.
1531  *		dbAllocAny() attempts to find the sufficient free space by
1533  *		highest level (i.e. L0, L1, L2) control page.  if free space
1534  *		large enough to satisfy the desired free space is found, the
1535  *		desired free space is allocated.
1539  *	nblocks	 -  actual number of contiguous free blocks desired.
1540  *	l2nb	 -  log2 number of contiguous free blocks desired.
1557 	 * down the dmap control levels for sufficient free space.  in dbAllocAny()
1558 	 * if free space is found, dbFindCtl() returns the starting  in dbAllocAny()
1560 	 * range of free space.  in dbAllocAny()
1579  * FUNCTION:	attempt to discard (TRIM) all free blocks of specific AG
1585  *		3) mark the blocks free again
1649 			/* the whole ag is free, trim now */  in dbDiscardAG()
1691  *		contiguous free blocks large enough to satisfy an allocation
1692  *		request for the specified number of free blocks.
1694  *		if sufficient contiguous free blocks are found, this routine
1696  *		contains or starts a range of contiqious free blocks that
1702  *	l2nb	-  log2 number of contiguous free blocks desired.
1705  *		   that contains or starts a range of contiguous free blocks.
1725 	 * sufficient free blocks.  in dbFindCtl()
1746 		 * sufficient free space.  if sufficient free space is found,  in dbFindCtl()
1748 		 * free space was found.  in dbFindCtl()
1768 		 * the dmap control page (i.e. the leaf) at which free  in dbFindCtl()
1795  *		free space.  the result of successful searches by these
1797  *		the dmaps themselves containing the desired contiguous free
1798  *		space or starting a contiguous free space of desired size
1811  *		upon the dmap's dmtree to find the requested contiguous free
1813  *		requested free space will start at the first block of the
1818  *	nblocks	 -  actual number of contiguous free blocks to allocate.
1819  *	l2nb	 -  log2 number of contiguous free blocks to allocate.
1880 		/* the dmap better be all free.  in dbAllocCtl()
1885 				  "the dmap is not all free\n");  in dbAllocCtl()
1937 		/* free the blocks is this dmap.  in dbAllocCtl()
1994 	 * free space.  if sufficient free space is found, dbFindLeaf()  in dbAllocDmapLev()
1995 	 * returns the index of the leaf at which free space was found.  in dbAllocDmapLev()
2001 	 * to the leaf at which free space was found.  in dbAllocDmapLev()
2005 	/* if not all bits of the dmap word are free, get the starting  in dbAllocDmapLev()
2006 	 * bit number within the dmap word of the required string of free  in dbAllocDmapLev()
2028  *		block range causes the maximum string of free blocks within
2053 	/* save the current value of the root (i.e. maximum free string)  in dbAllocDmap()
2084  *		causes the maximum string of free blocks within the dmap to
2092  *	dp	-  pointer to dmap to free the block range from.
2108 	/* save the current value of the root (i.e. maximum free string)  in dbFreeDmap()
2113 	/* free the specified (blocks) bits */  in dbFreeDmap()
2192 	 * dmap words will be marked as free in a single shot and the leaves  in dbAllocBits()
2193 	 * will be updated. a single leaf may describe the free space of  in dbAllocBits()
2268 	/* update the free count for this dmap */  in dbAllocBits()
2273 	/* if this allocation group is completely free,  in dbAllocBits()
2281 	/* update the free count for the allocation group and map */  in dbAllocBits()
2292  * FUNCTION:	free a specified block range from a dmap.
2303  *	dp	-  pointer to dmap to free bits from.
2329 	/* free the bits of the dmaps words corresponding to the block range.  in dbFreeBits()
2337 	 * be marked as free in a single shot and the leaves will be updated. a  in dbFreeBits()
2338 	 * single leaf may describe the free space of multiple dmap words,  in dbFreeBits()
2356 			/* free (zero) the appropriate bits within this  in dbFreeBits()
2374 			 * words and free (zero) the bits of these words.  in dbFreeBits()
2411 	/* update the free count for this dmap.  in dbFreeBits()
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()
2458  *		maximum string of free blocks (i.e. a change in the root
2526 	 * maximum l2 free string described by this dmapctl).  in dbAdjCtl()
2610 			 * of the maximum free buddy system.  in dbAdjCtl()
2615 					  "the maximum free buddy is not the old root\n");  in dbAdjCtl()
2940  * FUNCTION:	search a dmtree_t for sufficient free blocks, returning
2941  *		the index of a leaf describing the free blocks if
2942  *		sufficient free blocks are found.
2946  *		free space.
2950  *	l2nb	- log2 number of free blocks to search for.
2952  *		  describing at least l2nb free blocks if sufficient
2953  *		  free blocks are found.
2957  *	-ENOSPC	- insufficient free blocks.
2964 	 * sufficient free space.  in dbFindLeaf()
2969 	/* sufficient free space available. now search down the tree  in dbFindLeaf()
2971 	 * describes sufficient free space.  in dbFindLeaf()
2979 			/* sufficient free space found.  move to the next  in dbFindLeaf()
2993 	 * free space.  in dbFindLeaf()
3004  * FUNCTION:	find a specified number of binary buddy free bits within a
3007  *		this routine searches the bitmap value for (1 << l2nb) free
3012  *	l2nb	-  number of free bits specified as a log2 number.
3015  *	starting bit number of free bits.
3028 	 * free bits) and compute the mask.  in dbFindBits()
3033 	/* scan the word for nb free bits at nb alignments.  in dbFindBits()
3051  * FUNCTION:	determine the largest binary buddy string of free
3058  *	largest binary buddy of free bits within a dmap word.
3064 	/* check if the wmap word is all free. if so, the  in dbMaxBud()
3065 	 * free buddy size is BUDMIN.  in dbMaxBud()
3070 	/* check if the wmap word is half free. if so, the  in dbMaxBud()
3071 	 * free buddy size is BUDMIN-1.  in dbMaxBud()
3076 	/* not all free or half free. determine the free buddy  in dbMaxBud()
3258 	/* save the current value of the root (i.e. maximum free string)  in dbAllocDmapBU()
3280 	 * dmap words will be marked as free in a single shot and the leaves  in dbAllocDmapBU()
3281 	 * will be updated. a single leaf may describe the free space of  in dbAllocDmapBU()
3317 	/* update the free count for this dmap */  in dbAllocDmapBU()
3325 	/* if this allocation group is completely free,  in dbAllocDmapBU()
3333 	/* update the free count for the allocation group and map */  in dbAllocDmapBU()
3656 	 * (the leftmost ag with average free space in it);  in dbFinalizeBmap()
3673 	/* determine how many free blocks are in the active  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()
3682 	 * group with average free space.  in dbFinalizeBmap()
3723  *		at entry, the bitmaps had been initialized as free (ZEROS);
3759 	 * free the bits corresponding to the block range (ZEROS):  in dbInitDmap()
3766 		/* number of bits to free in the word */  in dbInitDmap()
3771 			/* free (set to 0) from the bitmap word */  in dbInitDmap()
3780 			/* free (set to 0) contiguous bitmap words */  in dbInitDmap()
3832  *	treemax	- will be filled in with max free for this dmap
3834  * RETURNS:	max free string at the root of the tree
3880  * RETURNS: max free string at the root of the tree
3890 	/* Determine the maximum free string possible for the leaves */  in dbInitTree()
3898 	 * can be combined if both buddies have a maximum free of l2min;  in dbInitTree()
3900 	 * a maximum free of l2min+1.  in dbInitTree()
3903 	 * the next maximum free (current free + 1).  in dbInitTree()
3905 	 * yields maximum free.  in dbInitTree()
3916 			/* coalesce if both adjacent buddies are max free */  in dbInitTree()
3928 	 * the higher level parent node are compared for a maximum free and  in dbInitTree()