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()
1661  *		contiguous free blocks large enough to satisfy an allocation
1662  *		request for the specified number of free blocks.
1664  *		if sufficient contiguous free blocks are found, this routine
1666  *		contains or starts a range of contiqious free blocks that
1672  *	l2nb	-  log2 number of contiguous free blocks desired.
1675  *		   that contains or starts a range of contiguous free blocks.
1695 	 * sufficient free blocks.  in dbFindCtl()
1716 		 * sufficient free space.  if sufficient free space is found,  in dbFindCtl()
1718 		 * free space was found.  in dbFindCtl()
1738 		 * the dmap control page (i.e. the leaf) at which free  in dbFindCtl()
1765  *		free space.  the result of successful searches by these
1767  *		the dmaps themselves containing the desired contiguous free
1768  *		space or starting a contiguous free space of desired size
1781  *		upon the dmap's dmtree to find the requested contiguous free
1783  *		requested free space will start at the first block of the
1788  *	nblocks	 -  actual number of contiguous free blocks to allocate.
1789  *	l2nb	 -  log2 number of contiguous free blocks to allocate.
1850 		/* the dmap better be all free.  in dbAllocCtl()
1855 				  "the dmap is not all free\n");  in dbAllocCtl()
1907 		/* free the blocks is this dmap.  in dbAllocCtl()
1964 	 * free space.  if sufficient free space is found, dbFindLeaf()  in dbAllocDmapLev()
1965 	 * returns the index of the leaf at which free space was found.  in dbAllocDmapLev()
1974 	 * to the leaf at which free space was found.  in dbAllocDmapLev()
1978 	/* if not all bits of the dmap word are free, get the starting  in dbAllocDmapLev()
1979 	 * bit number within the dmap word of the required string of free  in dbAllocDmapLev()
2001  *		block range causes the maximum string of free blocks within
2026 	/* save the current value of the root (i.e. maximum free string)  in dbAllocDmap()
2057  *		causes the maximum string of free blocks within the dmap to
2065  *	dp	-  pointer to dmap to free the block range from.
2081 	/* save the current value of the root (i.e. maximum free string)  in dbFreeDmap()
2086 	/* free the specified (blocks) bits */  in dbFreeDmap()
2165 	 * dmap words will be marked as free in a single shot and the leaves  in dbAllocBits()
2166 	 * will be updated. a single leaf may describe the free space of  in dbAllocBits()
2241 	/* update the free count for this dmap */  in dbAllocBits()
2246 	/* if this allocation group is completely free,  in dbAllocBits()
2254 	/* update the free count for the allocation group and map */  in dbAllocBits()
2265  * FUNCTION:	free a specified block range from a dmap.
2276  *	dp	-  pointer to dmap to free bits from.
2302 	/* free the bits of the dmaps words corresponding to the block range.  in dbFreeBits()
2310 	 * be marked as free in a single shot and the leaves will be updated. a  in dbFreeBits()
2311 	 * single leaf may describe the free space of multiple dmap words,  in dbFreeBits()
2329 			/* free (zero) the appropriate bits within this  in dbFreeBits()
2347 			 * words and free (zero) the bits of these words.  in dbFreeBits()
2384 	/* update the free count for this dmap.  in dbFreeBits()
2390 	/* update the free count for the allocation group and  in dbFreeBits()
2397 	/* check if this allocation group is not completely free and  in dbFreeBits()
2431  *		maximum string of free blocks (i.e. a change in the root
2499 	 * maximum l2 free string described by this dmapctl).  in dbAdjCtl()
2587 			 * of the maximum free buddy system.  in dbAdjCtl()
2592 					  "the maximum free buddy is not the old root\n");  in dbAdjCtl()
2922  * FUNCTION:	search a dmtree_t for sufficient free blocks, returning
2923  *		the index of a leaf describing the free blocks if
2924  *		sufficient free blocks are found.
2928  *		free space.
2932  *	l2nb	- log2 number of free blocks to search for.
2934  *		  describing at least l2nb free blocks if sufficient
2935  *		  free blocks are found.
2940  *	-ENOSPC	- insufficient free blocks.
2950 	 * sufficient free space.  in dbFindLeaf()
2955 	/* sufficient free space available. now search down the tree  in dbFindLeaf()
2957 	 * describes sufficient free space.  in dbFindLeaf()
2965 			/* sufficient free space found.  move to the next  in dbFindLeaf()
2981 	 * free space.  in dbFindLeaf()
2992  * FUNCTION:	find a specified number of binary buddy free bits within a
2995  *		this routine searches the bitmap value for (1 << l2nb) free
3000  *	l2nb	-  number of free bits specified as a log2 number.
3003  *	starting bit number of free bits.
3016 	 * free bits) and compute the mask.  in dbFindBits()
3021 	/* scan the word for nb free bits at nb alignments.  in dbFindBits()
3039  * FUNCTION:	determine the largest binary buddy string of free
3046  *	largest binary buddy of free bits within a dmap word.
3052 	/* check if the wmap word is all free. if so, the  in dbMaxBud()
3053 	 * free buddy size is BUDMIN.  in dbMaxBud()
3058 	/* check if the wmap word is half free. if so, the  in dbMaxBud()
3059 	 * free buddy size is BUDMIN-1.  in dbMaxBud()
3064 	/* not all free or half free. determine the free buddy  in dbMaxBud()
3246 	/* save the current value of the root (i.e. maximum free string)  in dbAllocDmapBU()
3268 	 * dmap words will be marked as free in a single shot and the leaves  in dbAllocDmapBU()
3269 	 * will be updated. a single leaf may describe the free space of  in dbAllocDmapBU()
3305 	/* update the free count for this dmap */  in dbAllocDmapBU()
3313 	/* if this allocation group is completely free,  in dbAllocDmapBU()
3321 	/* update the free count for the allocation group and map */  in dbAllocDmapBU()
3644 	 * (the leftmost ag with average free space in it);  in dbFinalizeBmap()
3661 	/* determine how many free blocks are in the active  in dbFinalizeBmap()
3662 	 * allocation groups plus the average number of free blocks  in dbFinalizeBmap()
3668 	/* if the preferred allocation group has not average free space.  in dbFinalizeBmap()
3670 	 * group with average free space.  in dbFinalizeBmap()
3711  *		at entry, the bitmaps had been initialized as free (ZEROS);
3747 	 * free the bits corresponding to the block range (ZEROS):  in dbInitDmap()
3754 		/* number of bits to free in the word */  in dbInitDmap()
3759 			/* free (set to 0) from the bitmap word */  in dbInitDmap()
3768 			/* free (set to 0) contiguous bitmap words */  in dbInitDmap()
3820  *	treemax	- will be filled in with max free for this dmap
3822  * RETURNS:	max free string at the root of the tree
3868  * RETURNS: max free string at the root of the tree
3878 	/* Determine the maximum free string possible for the leaves */  in dbInitTree()
3886 	 * can be combined if both buddies have a maximum free of l2min;  in dbInitTree()
3888 	 * a maximum free of l2min+1.  in dbInitTree()
3891 	 * the next maximum free (current free + 1).  in dbInitTree()
3893 	 * yields maximum free.  in dbInitTree()
3904 			/* coalesce if both adjacent buddies are max free */  in dbInitTree()
3916 	 * the higher level parent node are compared for a maximum free and  in dbInitTree()