xnu-2050.24.15.tar.gz

[apple/xnu.git] / bsd / hfs / hfscommon / Misc / HybridAllocator.c

/*
 * 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