--- /dev/null
+/*
+ * Copyright (c) 2009 Apple Inc. All rights reserved.
+ *
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
+ *
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. The rights granted to you under the License
+ * may not be used to create, or enable the creation or redistribution of,
+ * unlawful or unlicensed copies of an Apple operating system, or to
+ * circumvent, violate, or enable the circumvention or violation of, any
+ * terms of an Apple operating system software license agreement.
+ *
+ * Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this file.
+ *
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ *
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
+ */
+
+#if CONFIG_HFS_ALLOC_RBTREE
+
+#define assert(a) { if (!(a)) { panic("File "__FILE__", line %d: assertion '%s' failed.\n", __LINE__, #a); } }
+
+//#include <sys/systm.h>
+#include "../../hfs_macos_defs.h"
+#include "../headers/HybridAllocator.h"
+
+#define bool Boolean
+
+#define ALLOC_DEBUG 0
+
+/*
+ * The rb_wrap macro in RedBlackTree.h automatically generates the source for a variety of functions that
+ * operate on the red-black trees. The bodies of these automatically generated functions are the corresponding
+ * macro from RedBlackTree.h. For example, the extent_tree_length_new() function invokes the rb_new() macro.
+ * We re-define actual wrapper functions around them so that we can re-name them and adjust the functions
+ * that are available to the allocator in VolumeAllocation.c.
+ *
+ * Here are the functions that get automatically generated:
+ * Offset-Tree Functions:
+ *
+ * initialize the tree
+ * static void extent_tree_offset_new(extent_tree_offset_t * tree)
+ *
+ * Get the first node in the tree. If it is empty, return NULL
+ * static extent_node_t* extent_tree_offset_first (extent_tree_offset_t * tree)
+ *
+ * Get the last node in the tree. If it is empty, return NULL
+ * static extent_node_t* extent_tree_offset_last (extent_tree_offset_t * tree)
+ *
+ * From a given extent_node_t, grab the next one. If no next exists, return NULL
+ * static extent_node_t* extent_tree_offset_next (extent_tree_offset_t * tree, extent_node_t * node)
+ *
+ * From a given extent_node_t, grab the previous. If no prev exists, return NULL
+ * static extent_node_t* extent_tree_offset_prev(extent_tree_offset_t * tree, extent_node_t * node)
+ *
+ * Find a extent_node_t with the specified key (search by offset). If it does not exist, return NULL
+ * static extent_node_t* extent_tree_offset_search(extent_tree_offset_t * tree, extent_node_t * key)
+ *
+ * Find an extent node_t withthe specified key (offset). If it does not exist,
+ * either grab the next node, if possible, or return NULL
+ * static extent_node_t* extent_tree_offset_nsearch(extent_tree_offset_t * tree, extent_node_t * key)
+ *
+ * Find an extent_node_t with the specified key (offset). If it does not exist,
+ * either grab the previous node, if possible, or return NULL
+ * static extent_node_t* extent_tree_offset_psearch(extent_tree_offset_t * tree, extent_node_t * key)
+ *
+ * Insert the specified node into the tree.
+ * static void extent_tree_offset_insert(extent_tree_offset_t * tree, extent_node_t * node)
+ *
+ * Remove the specified node from the tree.
+ * static void extent_tree_offset_remove(extent_tree_offset_t * tree, extent_node_t * node)
+ *
+ */
+
+
+/* Static Functions only used in this file */
+static int32_t
+extent_tree_internal_alloc_space(extent_tree_offset_t *offset_tree,
+ u_int32_t size, u_int32_t offset, extent_node_t *node);
+
+/*
+ * cmp_offset_node
+ *
+ * Compare the extents in two nodes by offset.
+ *
+ * Returns:
+ * -1 if node 1's offset < node 2's offset.
+ * 1 if node 1's offset > node 2's offset.
+ */
+
+__private_extern__ int
+cmp_offset_node(extent_node_t *node_1, extent_node_t *node_2) {
+ u_int32_t addr_1 = node_1->offset;
+ u_int32_t addr_2 = node_2->offset;
+
+ return ((addr_1 > addr_2) - (addr_1 < addr_2));
+}
+
+/*
+ * Allocate a new red-black tree node.
+ *
+ * Currently, we get memory from the M_TEMP zone.
+ * TODO: Need to get our own zone to avoid bloating the M_TEMP zone.
+ */
+__private_extern__ extent_node_t *
+alloc_node(u_int32_t length, u_int32_t offset) {
+ extent_node_t *node;
+ MALLOC(node, extent_node_t *, sizeof(extent_node_t), M_TEMP, M_WAITOK);
+
+ if (node) {
+ node->offset = offset;
+ node->length = length;
+ node->offset_next = NULL;
+ }
+ return node;
+}
+
+/*
+ * De-allocate a red-black tree node.
+ *
+ * Currently, this goes back to the M_TEMP zone.
+ * TODO: May need to adjust this if we pull memory out of our own zone.
+ */
+__private_extern__ void
+free_node(extent_node_t *node) {
+ FREE(node, M_TEMP);
+}
+
+/*
+ * rb_wrap is a macro found in the rb.h header file. It builds functions that operate on
+ * the red-black tree based upon the types specified here. This code will build red-black tree
+ * search functions that operate on extent_node_t's and use cmp_length_node to do length searches.
+ * It uses cmp_offset_node to do offset searches. Ties are broken by offset. This will generate
+ * the functions specified above.
+ */
+
+rb_wrap(__attribute__ ((unused)) static, extent_tree_offset_, extent_tree_offset_t, extent_node_t, offset_link, cmp_offset_node)
+
+
+/*
+ * Create a new extent tree, composed of links sorted by offset.
+ */
+__private_extern__ void
+extent_tree_init(extent_tree_offset_t *offset_tree)
+{
+ extent_node_t *node = NULL;
+ extent_tree_offset_new(offset_tree);
+
+ node = extent_tree_off_first (offset_tree);
+ if (node) {
+ node->offset_next = NULL;
+ }
+}
+
+/*
+ * Destroy an extent tree
+ *
+ * This function finds the first node in the specified red-black tree, then
+ * uses the embedded linked list to walk through the tree in O(n) time and destroy
+ * all of its nodes.
+ */
+__private_extern__ void
+extent_tree_destroy(extent_tree_offset_t *off_tree) {
+ extent_node_t *node = NULL;
+ extent_node_t *next = NULL;
+
+ node = extent_tree_offset_first (off_tree);
+
+ while (node) {
+ next = node->offset_next;
+ extent_tree_offset_remove (off_tree, node);
+ free_node (node);
+ node = next;
+ }
+}
+
+/*
+ * Search the extent tree by offset. The "key" argument is only used to extract
+ * the offset and length information. Its link fields are not used in the underlying
+ * tree code.
+ */
+__private_extern__ extent_node_t *
+extent_tree_off_search(extent_tree_offset_t *tree, extent_node_t *key) {
+ return extent_tree_offset_search(tree, key);
+}
+
+/*
+ * Search the extent tree by offset, finding the next node in the tree
+ * if the specified one does not exist. The "key" argument is only used to extract
+ * the offset and length information. Its link fields are not used in the underlying
+ * tree code.
+ */
+__private_extern__ extent_node_t *
+extent_tree_off_search_next(extent_tree_offset_t *offset_tree, extent_node_t *key) {
+
+ return extent_tree_offset_nsearch (offset_tree, key);
+}
+
+/*
+ * Search the extent tree by offset to find a starting position. Then, do a linear search
+ * through the list of free extents to find the first free extent in the tree that has size
+ * greater than or equal to the specified size. The "key" argument is only used to extract
+ * the offset and length information. Its link fields are not used in the underlying
+ * tree code.
+ */
+__private_extern__ extent_node_t *
+extent_tree_off_search_nextWithSize (extent_tree_offset_t *offset_tree, extent_node_t *key) {
+
+ extent_node_t *current;
+
+ u_int32_t min_size = key->length;
+
+ current = extent_tree_offset_nsearch (offset_tree, key);
+
+ while (current) {
+ if (current->length >= min_size) {
+ return current;
+ }
+ current = current->offset_next;
+ }
+
+ /* return NULL if no free extent of suitable size could be found. */
+ return NULL;
+}
+
+
+/*
+ * Search the extent tree by offset, finding the previous node in the tree
+ * if the specified one does not exist. The "key" argument is only used to extract
+ * the offset and length information. Its link fields are not used in the underlying
+ * tree code.
+ */
+__private_extern__ extent_node_t *
+extent_tree_off_search_prev(extent_tree_offset_t *offset_tree, extent_node_t *key) {
+
+ return extent_tree_offset_psearch (offset_tree, key);
+}
+
+
+/*
+ * Find the first node in the extent tree, by offset. This will be the first
+ * free space region relative to the start of the disk.
+ */
+__private_extern__ extent_node_t *
+extent_tree_off_first (extent_tree_offset_t *offset_tree) {
+ return extent_tree_offset_first(offset_tree);
+}
+
+/*
+ * From a given tree node (sorted by offset), get the next node in the tree.
+ */
+__private_extern__ extent_node_t *
+extent_tree_off_next(extent_tree_offset_t * tree, extent_node_t *node)
+{
+ return extent_tree_offset_next(tree, node);
+}
+
+/*
+ * From a given tree node (sorted by offset), get the previous node in the tree.
+ */
+__private_extern__ extent_node_t *
+extent_tree_off_prev(extent_tree_offset_t * tree, extent_node_t *node)
+{
+ return extent_tree_offset_prev(tree, node);
+}
+
+
+/*
+ * For a node of a given offset and size, remove it from the extent tree and
+ * insert a new node that:
+ *
+ * A) increase its offset by that of the node we just removed
+ * B) decreases its size by that of the node we just removed.
+ *
+ * NOTE: Callers must ensure that the 'size' specified is less than or equal to the
+ * length of the extent represented by node. The node pointer must point to an
+ * extant node in the tree, as it will be removed from the tree.
+ */
+static int32_t
+extent_tree_internal_alloc_space(extent_tree_offset_t *offset_tree, u_int32_t size,
+ u_int32_t offset, extent_node_t *node)
+{
+ if (node) {
+ extent_node_t *prev = NULL;
+ extent_node_t *next = NULL;
+
+ if( ALLOC_DEBUG ) {
+ assert ((size <= node->length));
+ assert ((offset == node->offset));
+ }
+
+ prev = extent_tree_offset_prev(offset_tree, node);
+
+ /*
+ * Note that, unless the node is exactly the size of the amount of space
+ * requested, we do not need to remove it from the offset tree, now matter
+ * how much space we remove from the node. Remember that the offset tree is
+ * sorting the extents based on their offsets, and that each node is a discrete
+ * chunk of free space.
+ *
+ * If node A has offset B, with length C, in the offset tree, by definition, there
+ * can be no other node in the extent tree within the range {B, B+C}. If there were,
+ * we'd have overlapped extents.
+ *
+ * So in the normal case, we'll just update the offset node in place with the new offset
+ * and size.
+ *
+ * Otherwise, if we have an exact match, then just remove the node altogether. Don't forget
+ * to update the next pointer for the linked list if applicable.
+ */
+ if (node->length == size) {
+ next = node->offset_next;
+ extent_tree_offset_remove(offset_tree, node);
+ free_node(node);
+ if (prev) {
+ prev->offset_next = next;
+ }
+ }
+ else {
+ node->offset = node->offset + size;
+ node->length -= size;
+ /* The next pointer does not change since we keep the node in place */
+ }
+ return 0;
+ }
+ return -1;
+}
+
+/*
+ * Search the extent tree for a region of free space after the specified
+ * offset and attempt to allocate it.
+ *
+ * This is expected to be used by attempts to grow a file contiguously. If we
+ * start at a file's EOF, then we can try to allocate space immediately after it
+ * if it's available. This function specifies a tail (the offset), and then passes it
+ * into extent_tree_offset_search. Note that this is not the search_prev or search_next
+ * variant, so if no node exists at the specified offset we'll fail out.
+ *
+ */
+
+__private_extern__ int32_t
+extent_tree_offset_alloc_space(extent_tree_offset_t *offset_tree, u_int32_t size, u_int32_t offset) {
+ extent_node_t search_sentinel = { .offset = offset };
+ extent_node_t *node = extent_tree_offset_search(offset_tree, &search_sentinel);
+ if (node && (node->length < size)) {
+ /* It's too small. Fail the allocation */
+ if ( ALLOC_DEBUG ) {
+ printf("HFS Allocator: internal_alloc_space, ptr (%p) node->length (%d), node->offset (%d), off(%d), size (%d) \n",
+ node, node->length, node->offset, offset, size);
+ }
+ return -1;
+ }
+ return extent_tree_internal_alloc_space(offset_tree, size, offset, node);
+}
+
+
+/*
+ * Search the extent tree for a region of free space at the specified
+ * offset and attempt to allocate it.
+ *
+ * This is a little bit more involved than the previous function. It is intended for use when
+ * we may be allocating space from the middle of an existing extent node.
+ *
+ */
+
+
+__private_extern__ int32_t
+extent_tree_offset_alloc_unaligned(extent_tree_offset_t *offset_tree, u_int32_t size, u_int32_t offset) {
+ extent_node_t search_sentinel = { .offset = offset };
+ extent_node_t *node= NULL;
+
+ node = extent_tree_off_search_prev(offset_tree, &search_sentinel);
+
+ if (node == NULL) {
+ return -1;
+ }
+
+ if (node && (node->length < size)) {
+ /* It's too small. Fail the allocation */
+ if ( ALLOC_DEBUG ) {
+ printf("HFS Allocator: internal_alloc_space, ptr (%p) node->length (%d), node->offset (%d), off(%d), size (%d) \n",
+ node, node->length, node->offset, offset, size);
+ }
+ return -1;
+ }
+
+ /* Now see if we need to split this node because we're not allocating from the beginning */
+ if (offset != node->offset) {
+
+ if (ALLOC_DEBUG) {
+ assert ((offset + size) <= (node->offset + node->length));
+ if (node->offset_next) {
+ assert ((offset > node->offset) && (offset < node->offset_next->offset));
+ }
+ }
+
+ u_int32_t end = node->offset + node->length;
+ node->length = offset - node->offset;
+
+ /*
+ * Do we need to create a new node? If our extent we're carving away ends earlier than
+ * the current extent's length, then yes - we do.
+ */
+ if ((offset + size) < (end)) {
+ u_int32_t newoff = offset + size;
+ u_int32_t newlen = end - newoff;
+
+ extent_node_t* newnode = alloc_node(newlen, newoff);
+ extent_tree_offset_insert(offset_tree, newnode);
+
+ extent_node_t *next = extent_tree_offset_next(offset_tree, newnode);
+ newnode->offset_next = next;
+ node->offset_next = newnode;
+ }
+
+ return 0;
+ }
+ else {
+ return extent_tree_internal_alloc_space(offset_tree, size, offset, node);
+ }
+}
+
+
+
+/*
+ * Mark an extent of space as being free. This means we need to insert
+ * this extent into our tree.
+ *
+ * Search the offset tree, based on the new offset that we construct by adding
+ * the length of our extent to be freed to its offset. If something exists at
+ * that offset, then we coalesce the nodes. In this case, we do not need to adjust
+ * the offset tree because our extent we wanted to add could not have been in the tree.
+ *
+ * If no node existed at the specified offset, then create a new one and insert it
+ * into the tree.
+ *
+ * Finally, search based on the node that would precede our newly created/inserted one.
+ * If possible, coalesce the previous node into our new one.
+ *
+ * We return the node which we are modifying in this function.
+ */
+
+__private_extern__ extent_node_t *
+extent_tree_free_space(extent_tree_offset_t *offset_tree, u_int32_t size, u_int32_t offset)
+{
+ extent_node_t *prev = NULL;
+ extent_node_t *node = NULL;
+ extent_node_t *next = NULL;
+ extent_node_t search_sentinel = { .offset = size + offset };
+
+ node = extent_tree_offset_nsearch(offset_tree, &search_sentinel);
+ /* Insert our node into the tree, and coalesce with the next one if necessary */
+
+ if ((node) && (node->offset == search_sentinel.offset)) {
+ node->offset = offset;
+ node->length += size;
+ next = node->offset_next;
+ }
+ else {
+ node = alloc_node(size, offset);
+ assert(node);
+ extent_tree_offset_insert(offset_tree, node);
+
+ /* Find the next entry in the tree, if applicable. */
+ next = extent_tree_offset_next(offset_tree, node);
+ node->offset_next = next;
+ }
+
+ /* Coalesce with the previous if necessary */
+ prev = extent_tree_offset_prev(offset_tree, node);
+ if (prev && (prev->offset + prev->length) == offset) {
+ extent_tree_offset_remove(offset_tree, prev);
+ node->offset = prev->offset;
+ node->length += prev->length;
+ free_node(prev);
+ prev = extent_tree_offset_prev(offset_tree, node);
+ }
+
+ /* Update the next pointer for the previous entry (if necessary) */
+ if (prev) {
+ prev->offset_next = node;
+ }
+
+ return node;
+}
+
+/*
+ * Remove the specified node from the offset_tree. Note that the parameter node
+ * must be an extant node in the tree. This function is used by the allocator when
+ * we are resizing a volume and need to directly manipulate the contents of the red-black
+ * tree without going through the normal allocation and deallocation routines.
+ */
+__private_extern__ void
+extent_tree_remove_node (extent_tree_offset_t *offset_tree, extent_node_t * node) {
+
+ if (node) {
+ /* Just remove the entry from the tree */
+ extent_tree_offset_remove(offset_tree, node);
+ }
+ return;
+
+}
+
+
+
+#if ALLOC_DEBUG
+/*
+ * For each node in the tree, print out its length and block offset.
+ */
+__private_extern__ void
+extent_tree_offset_print(extent_tree_offset_t *offset_tree)
+{
+ extent_node_t *node = NULL;
+
+ node = extent_tree_offset_first(offset_tree);
+ while (node) {
+ printf("length: %u, offset: %u\n", node->length, node->offset);
+ node = node->offset_next;
+ }
+}
+#endif
+
+#endif
projects / apple / xnu.git / blobdiff