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.
277 	/* free the memory for the in-memory bmap. */  in dbUnmount()
340  * FUNCTION:	free the specified block range from the working block
343  *		the blocks will be free from the working map one dmap
385 	 * free the blocks a dmap at a time.  in dbFree()
408 		/* free the blocks. */  in dbFree()
430  * FUNCTION:	update the allocation state (free or allocate) of the
438  *	free	- 'true' if block range is to be freed from the persistent
450 	     int free, s64 blkno, s64 nblocks, struct tblock * tblk)  in dbUpdatePMap()  argument
523 				/* update (free or allocate) the bits  in dbUpdatePMap()
528 				if (free)  in dbUpdatePMap()
544 				/* update (free or allocate) the bits  in dbUpdatePMap()
547 				if (free)  in dbUpdatePMap()
611  *		average free space.  It is the preferred group that we target
639 	/* determine the average number of free blocks within the ags. */  in dbNextAG()
652 	 * average free space.  in dbNextAG()
690  * FUNCTION:	attempt to allocate a specified number of contiguous free
775 	 * will start looking for free space starting at this point.  in dbAlloc()
791 		 * AG with sufficient free space.  in dbAlloc()
1073  *	nblocks	-  number of contiguous free blocks of the range.
1112 	 * is free.  in dbAllocNext()
1118 	 * if the block range is free.  not all bits of the first and  in dbAllocNext()
1122 	 * the actual bits to determine if they are free.  a single pass  in dbAllocNext()
1125 	 * tree will be examined to determine if the blocks are free. a  in dbAllocNext()
1126 	 * single leaf may describe the free space of multiple dmap  in dbAllocNext()
1140 			/* check if the bits are free.  in dbAllocNext()
1156 			 * if the blocks are free.  in dbAllocNext()
1159 				/* does the leaf describe any free space ?  in dbAllocNext()
1189  * FUNCTION:	attempt to allocate a number of contiguous free blocks near
1193  *		check the next four contiguous leaves for sufficient free
1194  *		space.  if sufficient free space is found, we'll allocate
1195  *		the desired free space.
1201  *	nblocks	-  actual number of contiguous free blocks desired.
1202  *	l2nb	-  log2 number of contiguous free blocks desired.
1234 	/* examine the leaves for sufficient free space.  in dbAllocNear()
1237 		/* does the leaf describe sufficient free space ?  in dbAllocNear()
1247 		/* if not all bits of the dmap word are free, get the  in dbAllocNear()
1249 		 * string of free bits and adjust the block number with the  in dbAllocNear()
1272  *		free blocks within the specified allocation group.
1276  *		find the required free space, if available.  we start the
1278  *		distinctly describes the allocation group's free space
1280  *		free space is not mixed in with that of any other group).
1283  *		describe the allocation group's free space.  at this height,
1284  *		the allocation group's free space may be represented by 1
1287  *		sufficient free space.  if sufficient free space is found,
1289  *		has free space.  once we have made it to the leaf, we
1293  *		sufficient free space and we allocate at this dmap.
1300  *		allocation group is completely free and we go to the first
1304  *		control pages to indicate no free space (NOFREE) within
1310  *	nblocks	-  actual number of contiguous free blocks desired.
1311  *	l2nb	-  log2 number of contiguous free blocks desired.
1346 	 * group size or if the allocation group is completely free. if  in dbAllocAG()
1354 	 * if the allocation group is completely free, dbAllocCtl() is  in dbAllocAG()
1357 	 * pages for free space when we know that free space exists.  second,  in dbAllocAG()
1359 	 * has no free space if the allocation group is part (not the first  in dbAllocAG()
1371 				  "dbAllocCtl failed in free AG\n");  in dbAllocAG()
1393 	 * the allocation group, looking for sufficient free space.  to begin,  in dbAllocAG()
1406 	 * subtrees for sufficient free space, starting with the leftmost  in dbAllocAG()
1410 		/* is there sufficient free space ?  in dbAllocAG()
1415 		/* sufficient free space found in a subtree. now search down  in dbAllocAG()
1417 		 * free space.  in dbAllocAG()
1461 			 * contains or starts off the free space.  in dbAllocAG()
1499  *		free blocks anywhere in the file system.
1501  *		dbAllocAny() attempts to find the sufficient free space by
1503  *		highest level (i.e. L0, L1, L2) control page.  if free space
1504  *		large enough to satisfy the desired free space is found, the
1505  *		desired free space is allocated.
1509  *	nblocks	 -  actual number of contiguous free blocks desired.
1510  *	l2nb	 -  log2 number of contiguous free blocks desired.
1527 	 * down the dmap control levels for sufficient free space.  in dbAllocAny()
1528 	 * if free space is found, dbFindCtl() returns the starting  in dbAllocAny()
1530 	 * range of free space.  in dbAllocAny()
1549  * FUNCTION:	attempt to discard (TRIM) all free blocks of specific AG
1555  *		3) mark the blocks free again
1619 			/* the whole ag is free, trim now */  in dbDiscardAG()
1663  *		contiguous free blocks large enough to satisfy an allocation
1664  *		request for the specified number of free blocks.
1666  *		if sufficient contiguous free blocks are found, this routine
1668  *		contains or starts a range of contiqious free blocks that
1674  *	l2nb	-  log2 number of contiguous free blocks desired.
1677  *		   that contains or starts a range of contiguous free blocks.
1697 	 * sufficient free blocks.  in dbFindCtl()
1718 		 * sufficient free space.  if sufficient free space is found,  in dbFindCtl()
1720 		 * free space was found.  in dbFindCtl()
1740 		 * the dmap control page (i.e. the leaf) at which free  in dbFindCtl()
1767  *		free space.  the result of successful searches by these
1769  *		the dmaps themselves containing the desired contiguous free
1770  *		space or starting a contiguous free space of desired size
1783  *		upon the dmap's dmtree to find the requested contiguous free
1785  *		requested free space will start at the first block of the
1790  *	nblocks	 -  actual number of contiguous free blocks to allocate.
1791  *	l2nb	 -  log2 number of contiguous free blocks to allocate.
1852 		/* the dmap better be all free.  in dbAllocCtl()
1857 				  "the dmap is not all free\n");  in dbAllocCtl()
1909 		/* free the blocks is this dmap.  in dbAllocCtl()
1966 	 * free space.  if sufficient free space is found, dbFindLeaf()  in dbAllocDmapLev()
1967 	 * returns the index of the leaf at which free space was found.  in dbAllocDmapLev()
1976 	 * to the leaf at which free space was found.  in dbAllocDmapLev()
1980 	/* if not all bits of the dmap word are free, get the starting  in dbAllocDmapLev()
1981 	 * bit number within the dmap word of the required string of free  in dbAllocDmapLev()
2003  *		block range causes the maximum string of free blocks within
2028 	/* save the current value of the root (i.e. maximum free string)  in dbAllocDmap()
2059  *		causes the maximum string of free blocks within the dmap to
2067  *	dp	-  pointer to dmap to free the block range from.
2083 	/* save the current value of the root (i.e. maximum free string)  in dbFreeDmap()
2088 	/* free the specified (blocks) bits */  in dbFreeDmap()
2167 	 * dmap words will be marked as free in a single shot and the leaves  in dbAllocBits()
2168 	 * will be updated. a single leaf may describe the free space of  in dbAllocBits()
2243 	/* update the free count for this dmap */  in dbAllocBits()
2248 	/* if this allocation group is completely free,  in dbAllocBits()
2256 	/* update the free count for the allocation group and map */  in dbAllocBits()
2267  * FUNCTION:	free a specified block range from a dmap.
2278  *	dp	-  pointer to dmap to free bits from.
2304 	/* free the bits of the dmaps words corresponding to the block range.  in dbFreeBits()
2312 	 * be marked as free in a single shot and the leaves will be updated. a  in dbFreeBits()
2313 	 * single leaf may describe the free space of multiple dmap words,  in dbFreeBits()
2331 			/* free (zero) the appropriate bits within this  in dbFreeBits()
2349 			 * words and free (zero) the bits of these words.  in dbFreeBits()
2386 	/* update the free count for this dmap.  in dbFreeBits()
2392 	/* update the free count for the allocation group and  in dbFreeBits()
2399 	/* check if this allocation group is not completely free and  in dbFreeBits()
2433  *		maximum string of free blocks (i.e. a change in the root
2501 	 * maximum l2 free string described by this dmapctl).  in dbAdjCtl()
2589 			 * of the maximum free buddy system.  in dbAdjCtl()
2594 					  "the maximum free buddy is not the old root\n");  in dbAdjCtl()
2924  * FUNCTION:	search a dmtree_t for sufficient free blocks, returning
2925  *		the index of a leaf describing the free blocks if
2926  *		sufficient free blocks are found.
2930  *		free space.
2934  *	l2nb	- log2 number of free blocks to search for.
2936  *		  describing at least l2nb free blocks if sufficient
2937  *		  free blocks are found.
2942  *	-ENOSPC	- insufficient free blocks.
2953 	 * sufficient free space.  in dbFindLeaf()
2958 	/* sufficient free space available. now search down the tree  in dbFindLeaf()
2960 	 * describes sufficient free space.  in dbFindLeaf()
2968 			/* sufficient free space found.  move to the next  in dbFindLeaf()
2986 	 * free space.  in dbFindLeaf()
2997  * FUNCTION:	find a specified number of binary buddy free bits within a
3000  *		this routine searches the bitmap value for (1 << l2nb) free
3005  *	l2nb	-  number of free bits specified as a log2 number.
3008  *	starting bit number of free bits.
3021 	 * free bits) and compute the mask.  in dbFindBits()
3026 	/* scan the word for nb free bits at nb alignments.  in dbFindBits()
3044  * FUNCTION:	determine the largest binary buddy string of free
3051  *	largest binary buddy of free bits within a dmap word.
3057 	/* check if the wmap word is all free. if so, the  in dbMaxBud()
3058 	 * free buddy size is BUDMIN.  in dbMaxBud()
3063 	/* check if the wmap word is half free. if so, the  in dbMaxBud()
3064 	 * free buddy size is BUDMIN-1.  in dbMaxBud()
3069 	/* not all free or half free. determine the free buddy  in dbMaxBud()
3251 	/* save the current value of the root (i.e. maximum free string)  in dbAllocDmapBU()
3273 	 * dmap words will be marked as free in a single shot and the leaves  in dbAllocDmapBU()
3274 	 * will be updated. a single leaf may describe the free space of  in dbAllocDmapBU()
3310 	/* update the free count for this dmap */  in dbAllocDmapBU()
3318 	/* if this allocation group is completely free,  in dbAllocDmapBU()
3326 	/* update the free count for the allocation group and map */  in dbAllocDmapBU()
3649 	 * (the leftmost ag with average free space in it);  in dbFinalizeBmap()
3666 	/* determine how many free blocks are in the active  in dbFinalizeBmap()
3667 	 * allocation groups plus the average number of free blocks  in dbFinalizeBmap()
3673 	/* if the preferred allocation group has not average free space.  in dbFinalizeBmap()
3675 	 * group with average free space.  in dbFinalizeBmap()
3716  *		at entry, the bitmaps had been initialized as free (ZEROS);
3752 	 * free the bits corresponding to the block range (ZEROS):  in dbInitDmap()
3759 		/* number of bits to free in the word */  in dbInitDmap()
3764 			/* free (set to 0) from the bitmap word */  in dbInitDmap()
3773 			/* free (set to 0) contiguous bitmap words */  in dbInitDmap()
3825  *	treemax	- will be filled in with max free for this dmap
3827  * RETURNS:	max free string at the root of the tree
3873  * RETURNS: max free string at the root of the tree
3883 	/* Determine the maximum free string possible for the leaves */  in dbInitTree()
3891 	 * can be combined if both buddies have a maximum free of l2min;  in dbInitTree()
3893 	 * a maximum free of l2min+1.  in dbInitTree()
3896 	 * the next maximum free (current free + 1).  in dbInitTree()
3898 	 * yields maximum free.  in dbInitTree()
3909 			/* coalesce if both adjacent buddies are max free */  in dbInitTree()
3921 	 * the higher level parent node are compared for a maximum free and  in dbInitTree()