fs/jfs/jfs_dmap.c

1087 	s8 *leaf;
1097 	leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1111 	/* check if the starting leaf indicates that anything
1114 	if (leaf[word] == NOFREE)
1126 	 * single leaf may describe the free space of multiple dmap
1159 				/* does the leaf describe any free space ?
1161 				if (leaf[word] < BUDMIN)
1165 				 * by this leaf.
1168 				    min_t(int, leaf[word], NLSTOL2BSZ(nwords));
1192  *		starting with the dmap leaf that covers the hint, we'll
1218 	s8 *leaf;
1225 	leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);
1237 		/* does the leaf describe sufficient free space ?
1239 		if (leaf[word] < l2nb)
1252 		if (leaf[word] < BUDMIN)
1288  *		the subtree is searched to find the leftmost leaf that
1289  *		has free space.  once we have made it to the leaf, we
1291  *		corresponding to this leaf.  we continue down the dmap control
1416 		 * the subtree to find the leftmost leaf that describes this
1435 		 * that corresponds to this leaf.
1717 		 * dbFindLeaf() returns the index of the leaf at which
1738 		 * the dmap control page (i.e. the leaf) at which free
1965 	 * returns the index of the leaf at which free space was found.
1974 	 * to the leaf at which free space was found.
2143 	s8 *leaf;
2146 	leaf = dp->tree.stree + LEAFIND;
2162 	 * updating the leaf corresponding to the dmap word. a single pass
2166 	 * will be updated. a single leaf may describe the free space of
2186 			/* update the leaf for this dmap word. in addition
2187 			 * to setting the leaf value to the binary buddy max
2212 				if (leaf[word] < BUDMIN) {
2214 						  "leaf page corrupt\n");
2218 				/* determine what the leaf value should be
2221 				 * of bits currently described by this leaf.
2223 				size = min_t(int, leaf[word],
2226 				/* update the leaf to reflect the allocation.
2227 				 * in addition to setting the leaf value to
2307 	 * the leaf corresponding to the dmap word. a single pass will be used
2311 	 * single leaf may describe the free space of multiple dmap words,
2315 	 * dbJoin() is used to update leaf values and will join the binary
2316 	 * buddy system of the leaves if the new leaf values indicate this
2336 			/* update the leaf for this dmap word.
2360 				/* determine what the leaf value should be
2363 				 * of bits that can be described by this leaf.
2370 				/* update the leaf.
2439  *		is respresented by a single leaf of the current dmapctl
2440  *		and the leaf will be updated with this value, possibly
2492 	/* determine the leaf number corresponding to the block and
2498 	/* save the current leaf value and the current root level (i.e.
2505 	 * if so, update the leaf to reflect the new leaf value using
2507 	 * the leaf with the new value.  in addition to updating the
2508 	 * leaf, dbSplit() will also split the binary buddy system of
2512 	 * the dmapctl tree as required by the new leaf value.
2609  * FUNCTION:	update the leaf of a dmtree with a new value, splitting
2610  *		the leaf from the binary buddy system of the dmtree's
2614  *	tp	- pointer to the tree containing the leaf.
2615  *	leafno	- the number of the leaf to be updated.
2616  *	splitsz	- the size the binary buddy system starting at the leaf
2618  *	newval	- the new value for the leaf.
2628 	s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2630 	/* check if the leaf needs to be split.
2632 	if (leaf[leafno] > tp->dmt_budmin) {
2634 		 * at the specified leaf until we reach the specified
2638 		cursz = leaf[leafno] - 1;
2644 			/* update the buddy's leaf with its new value.
2655 	/* adjust the dmap tree to reflect the specified leaf's new
2666  *		that hold a specified leaf until the specified leaf
2682  *	tp	- pointer to the tree containing the leaf.
2683  *	leafno	- the number of the leaf to be updated.
2693 	s8 *leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2695 	/* leaf should be part (not first part) of a binary
2698 	assert(leaf[leafno] == NOFREE);
2700 	/* the back split is accomplished by iteratively finding the leaf
2701 	 * that starts the buddy system that contains the specified leaf and
2703 	 * the specified leaf becomes the start of a buddy system.
2705 	 * determine maximum possible l2 size for the specified leaf.
2713 	 * the buddy system that contains the specified leaf.
2719 	while (leaf[leafno] == NOFREE) {
2720 		/* find the leftmost buddy leaf.
2735 			if (leaf[bud] != NOFREE) {
2736 				/* split the leaf at the start of the
2739 				cursz = leaf[bud] - 1;
2746 	if (leaf[leafno] != size) {
2747 		jfs_err("JFS: wrong leaf value in dbBackSplit");
2757  * FUNCTION:	update the leaf of a dmtree with a new value, joining
2758  *		the leaf with other leaves of the dmtree into a multi-leaf
2762  *	tp	- pointer to the tree containing the leaf.
2763  *	leafno	- the number of the leaf to be updated.
2764  *	newval	- the new value for the leaf.
2771 	s8 *leaf;
2773 	/* can the new leaf value require a join with other leaves ?
2778 		leaf = tp->dmt_stree + le32_to_cpu(tp->dmt_leafidx);
2780 		/* try to join the specified leaf into a large binary
2782 		 * the specified leafno with its buddy (leaf) at new value.
2783 		 * if the join occurs, we attempt to join the left leaf
2798 			/* get the buddy leaf.
2802 			/* if the leaf's new value is greater than its
2805 			if (newval > leaf[buddy])
2809 			if (newval < leaf[buddy])
2839 	/* update the leaf value.
2850  * FUNCTION:	update a leaf of a dmtree with a new value, adjusting
2851  *		the dmtree, as required, to reflect the new leaf value.
2857  *	leafno	- the number of the leaf to be updated.
2858  *	newval	- the new value for the leaf.
2869 	/* pick up the index of the leaf for this leafno.
2889 		/* get the index of the first leaf of the 4 leaf
2890 		 * group containing the specified leaf (leafno).
2894 		/* get the index of the parent of this 4 leaf group.
2912 		/* parent becomes leaf for next go-round.
2923  *		the index of a leaf describing the free blocks if
2927  *		proceeds down the tree to the leftmost leaf with sufficient
2933  *	leafidx	- return pointer to be set to the index of the leaf
2956 	 * starting at the next level for the leftmost leaf that
2980 	/* set the return to the leftmost leaf describing sufficient
3265 	 * updating the leaf corresponding to the dmap word. a single pass
3269 	 * will be updated. a single leaf may describe the free space of
3526 				 * initialize corresponding parent L0 leaf
3565 			 * initialize corresponding parent L1 leaf
3589 		 * initialize corresponding parent L2 leaf
3687 	 * at agheight level height (from leaf) with agwidth number of nodes
3838 	/* init each leaf from corresponding wmap word:
3839 	 * note: leaf is set to NOFREE(-1) if all blocks of corresponding
3859  *		configure binary buddy system at the leaf level, then
3860  *		bubble up the values of the leaf nodes up the tree.
3864  *	l2leaves- Number of leaf nodes as a power of 2
3865  *	l2min	- Number of blocks that can be covered by a leaf
3882 	 * configure the leaf level into binary buddy system
3887 	 * the combination will result in the left-most buddy leaf having
3915 	 * Starting at the leaf node level, the four nodes described by
3946 {				/* start leaf index not covered by range */