hfscommon/Misc/VolumeAllocation.c

51 					whether or not the red-black tree is enabled and call the appropriate function
55 					not the red-black tree is enabled and call the appropriate function if applicable.
59 					Since the red-black tree obviates the need to maintain the free extent cache, we do
60 					not update it if the tree is also live.  As a result, if we ever need to destroy the trees
70 					filesystem.  It is also used to shrink or grow the number of blocks that the red-black tree should
72 					number of items in the tree that we can allocate from.
81 	use the red-black tree code.
85 					and/or create Red-Black Tree allocation tree nodes to correspond
95 					we'll remove the appropriate entries from the red-black tree.
104 					called by the bitmap scanning logic as the red-black tree should be able
105 					to do this internally by searching its tree.
117 					the red-black tree.  We can just make an internal call to
131 					using the original HFS+ bitmap scanning logic.  The red-black tree
135 					using the new red/black tree data structure and search algorithms
136 					provided by the tree library.  Updates the red/black tree nodes after
170 					Test to see if the allocation red-black tree is live.  This function
172 					in the HFS mount structure, to prevent red-black tree pointers from disappearing.
175 					Test to see if the specified extent is marked as allocated in the red-black tree.
187 					red-black tree and then check the corresponding status in the bitmap file.  If the two are out
192 					Checks the embedded linked list structure of the red black tree for integrity.  The next pointer
198 					Build a red-black tree for the given filesystem's bitmap.
201 					Destroy the tree on the given filesystem
207 					the end of the block.  Free space extents are inserted into the appropriate red-black tree.
855 	 * in conjunction with the Generate Tree function.   If the red-black tree does not currently contain
856 	 * an allocation block of appropriate size, then start scanning blocks FOR the tree generation function until
857 	 * we find what we need.  We'll update the tree fields when we're done, indicating that we've advanced the
858 	 * high water mark for the tree.
937 		 * if we are using the new R/B tree allocator, since
971 				//TODO: only tear down tree if the tree is finished building.
973 				/* Tear down tree if we encounter an error */
982 				// fall through to the normal allocation since the rb-tree allocation failed.
995 		 * we are using the red-black tree for allocations.  If we jettison
996 		 * the tree, then we will reset the free-extent cache and start over.
1156 	 * If we're using the red-black tree code, then try to free the
1157 	 * blocks by marking them in the red-black tree first.  If the tree
1162 	 * Remember that we can get into this function if the tree isn't finished
1171 		 * that is currenly controlled by the r/b tree.
1444  * the blocks, so we will never dirty them as part of the tree building scan.
1564  * Variant of BlockAllocateContig that uses the newer red-black tree library
1565  * in order to manage free space extents.  This will search the red-black tree
1568  * Note that this function is invoked from both the red-black tree variant of BlockAllocateany
1629 		 * from the red-black tree after the bitmap has been updated on-disk.
1655 	 * we'll start by searching the offset tree rather than the normal length
1656 	 * tree. Note that this function can be invoked from BlockAllocateAny, in
1741 		 * when do we tear down the tree?  Or should the logic be in BlockAllocateContig??
1834  * the red-black allocation tree to figure out where the free ranges are.
1851 	/* If we're using the red-black tree, try searching at the specified offsets. */
2185  * as in-use.  It will mark the blocks in the red-black tree if appropriate.  We need to do
2186  * this logic here to avoid callers having to deal with whether or not the red-black tree
2207 			 * red-black tree.  Just update the bitmap and don't bother manipulating the tree
2244 			tree-based allocator is used, as all allocations must correctly
2245 			be marked on-disk.  If the tree-based approach is running, then
2246 			this will be done before the node is removed from the tree.
2421  * appropriate node from the tree.
2455 		 * Mark the blocks in the offset tree.
2490 	 * If we encountered a red-black tree error, for now, we immediately back off and force
2491 	 * destruction of rb-tree.  Set the persistent error-detected bit in the mount point.
2493 	 * not allow the rb-tree to be used.  On next mount, we will force a re-construction from
2515  * as freed.  It will mark the blocks in the red-black tree if appropriate.  We need to do
2516  * this logic here to avoid callers having to deal with whether or not the red-black tree
2535 			 * red-black tree.  Just update the bitmap and don't bother manipulating the tree
2907  * existing rb-tree node if possible, or else create a new one.
2934 		 * portion of the bitmap that is no longer controlled by the r/b tree.
2935 		 * In this case, just update the bitmap and do not attempt to manipulate the tree.
2947 			 * not in the offset tree, since it should be tracking free extents, rather than allocated
2959 				 * If the tree generation code has not yet finished scanning the
2962 				 * watermark on the offset tree, just bail out and let the scanner catch up with us.
2984 	 * If we encounter an error in adding the extents to the rb-tree, then immediately
2986 	 * to indicate we should not use the rb-tree until next mount, when we can force a rebuild.
3012 			as the red-black tree should be able to do this by internally
3013 			searching its tree.
3384 		 * If the region should be free, then we expect to see extents in the tree
3411  * compares their status in the red-black tree vs. the allocation bitmap.  If the two are out of sync
3414  * Because this function requires a red-black tree search to validate every allocation block, it is
3443  * This function iterates through the red-black tree's nodes, and then verifies that the linked list
3450 	extent_tree_offset_t *tree = &hfsmp->offset_tree;
3456 	current = extent_tree_off_first (tree);
3460 		treenext = extent_tree_off_next (tree, current);
3495 	 * With only one tree, then we just have to validate that there are entries
3496 	 * in the R/B tree at the specified offset if it really is free.
3774  * Check to see if the red-black tree is live.  Allocation file lock must be held
3776  * HFS is built without activating the red-black tree code.
3782 	//TODO: Update this function to deal with a truncate/resize coming in when the tree
3809  * Additionally, we may want an allocating thread to invoke this if the tree
3927  * use with the red-black tree validation code.  It assumes we're only checking whether
4006  * that enable us to initialize the tree.
4018  * buf_meta_breads to scan through the bitmap and re-build the tree state.
4050 	 * to scan them and add the results into the red-black tree.  We use the mount point
4085 		 * allocation bitmap lock for the entire duration of the tree scan.  For a first check-in
4090 		 *		abort tree-build.
4091 		 *		unset tree-in-progress bit.
4119 		printf("DestroyTrees: Validating red/black tree for vol %s\n", (char*) hfsmp->vcbVN);
4124 	 * extent_tree_destroy will start with the first entry in the tree (by offset), then
4125 	 * iterate through the tree quickly using its embedded linked list.  This results in tree
4145  * If we are using the red-black tree code then we need to account for the fact that
4146  * we may encounter situations where we need to jettison the tree.  If that is the
4189  * tree past the specified offset new_end_block.  In the growth case, we'll have to force
4204 	 * if the red/black tree is not enabled.
4220 		/* Remover points to the current item to free/remove from the tree */
4263 						 * we will stop representing bitmap values in the tree.  Just bail out now.
4269 					 * we'll need to start yanking things out of the tree, and make 'node'
4270 					 * the last element in the tree in the linked list.
4282 			 * the offset tree.  We'll simply iterate through the tree linked list, removing the current
4283 			 * element from the tree, freeing them as we come across them.
4329 		 * Don't forget to update offset_block_end after a successful tree extension.
4487 	/* If red-black tree is enabled, no free extent cache is necessary */
4618 	 * If using the red-black tree allocator, then there's no need to special case
4620 	 * to the red-black tree, where it will get sorted by offset and length.  The only special
4690 	/* Do not do anything if debug is not on, or if we're using the red-black tree */