klish/lub/heap/heap_raw_realloc.c

#include <string.h>
#include <assert.h>

#include "private.h"

/*--------------------------------------------------------- */
lub_heap_status_t
lub_heap_raw_realloc(lub_heap_t      *this,
                     char           **ptr,
                     size_t           requested_size,
                     lub_heap_align_t alignment)
{
    lub_heap_status_t result               = LUB_HEAP_FAILED;
    lub_heap_block_t *block                = NULL;
    words_t           words;
    char             *new_ptr              = NULL;
    const size_t      MIN_SIZE             = sizeof(lub_heap_free_block_t);
    /* make the minimum alignment leave enough space for 
     * (sizeof(lub_heap_free_block_t) + sizeof(lub_heap_alloc_block_t) + sizeof(lub_heap_node_t))
     * approx 72 bytes on 64-bit architecture
     */
    const lub_heap_align_t MIN_ALIGN_NON_NATIVE = LUB_HEAP_ALIGN_2_POWER_7;
    size_t                 size                 = requested_size;
    
    do
    {
        if(NULL == ptr) break; /* The client MUST give us a pointer to play with */
        
        if(LUB_HEAP_ZERO_ALLOC == *ptr)
        {
            *ptr = NULL;
        }
        if(*ptr && (BOOL_FALSE == lub_heap_validate_pointer(this,*ptr)))
        {
            /* This is not a valid pointer */
            result = LUB_HEAP_INVALID_POINTER;
            break;
        }
        /* check the heap integrity */
        if(BOOL_FALSE == lub_heap_check_memory(this))
        {
            result = LUB_HEAP_CORRUPTED;
            break;
        }
        
        if(size)
        {
            /* make sure we get enough space for the header/tail */
            size += sizeof(lub_heap_alloc_block_t);

            /* make sure we are at least natively aligned */
            size += (LUB_HEAP_ALIGN_NATIVE-1);
            size &= ~(LUB_HEAP_ALIGN_NATIVE-1);

            if(size < MIN_SIZE)
            {
                /* 
                 * we must ensure that any allocated block is at least
                 * large enough to hold a free block node when it is released
                 */
                size = MIN_SIZE;
            }
            if(LUB_HEAP_ALIGN_NATIVE != alignment)
            {
                if(alignment < MIN_ALIGN_NON_NATIVE)
                {
                    /*
                     * ensure that we always leave enough space
                     * to be able to collapse the block to the 
                     * right size
                     */
                    alignment = MIN_ALIGN_NON_NATIVE;
                }
                /* add twice the alignment */
                size  += (alignment << 1);
            }
        }
        words = (size >> 2);

        if(requested_size > size)
        {
            /* the size has wrapped when accounting for overheads */
            break;
        }
        if(NULL != *ptr)
        {
            /* get reference to the current block */
            block = lub_heap_block_from_ptr(*ptr);
    
            /* first of all check this is an allocated block */
            if(1 == block->alloc.tag.free)
            {
                result = LUB_HEAP_DOUBLE_FREE;
                break;
            }
            /* first of all check this is an allocated block */
            if(BOOL_FALSE == lub_heap_block_check(block))
            {
                result = LUB_HEAP_CORRUPTED;
                break;
            }
            /* is the current block large enough for the request */
            if(words && (block->alloc.tag.words >= words))
            {
                lub_heap_block_t *next_block = lub_heap_block_getnext(block);
                words_t           delta      = (block->alloc.tag.words - words);
                lub_heap_tag_t   *tail;
    
                result = LUB_HEAP_OK;
                new_ptr = *ptr;
                
                if(delta && (NULL != next_block) )
                {
                    /* can we graft this spare memory to a following free block? */
                    if(1 == next_block->free.tag.free)
                    {
                        
                        block->alloc.tag.words = words;
                        tail = lub_heap_block__get_tail(block);
                        tail->words   = words;
                        tail->free    = 0;
                        tail->segment = 0;
                        
                        lub_heap_graft_to_bottom(this,
                                                 next_block,
                                                 &tail[1],
                                                 delta,
                                                 BOOL_FALSE,
                                                 BOOL_FALSE);
                        this->stats.alloc_bytes -= (delta << 2);
                        break;
                    }
                }
                /* Is there enough space to turn the spare memory into a free block? */
                if(delta >= (sizeof(lub_heap_free_block_t) >> 2))
                {
                    tail = lub_heap_block__get_tail(block);
                    
                    lub_heap_init_free_block(this,
                                             &tail[1-delta],
                                             (delta << 2),
                                             BOOL_FALSE,
                                             tail->segment);

                    block->alloc.tag.words = words;
                    tail = lub_heap_block__get_tail(block);
                    tail->words   = words;
                    tail->free    = 0;
                    tail->segment = 0;
                    this->stats.alloc_bytes -= (delta << 2);
                 }
                break;
            }
            else if(words)
            {
                /* can we simple extend the current allocated block? */
                if(    (BOOL_TRUE == lub_heap_extend_upwards  (this,&block,words))
                    || (BOOL_TRUE == lub_heap_extend_downwards(this,&block,words))
                    || (BOOL_TRUE == lub_heap_extend_both_ways(this,&block,words)) )
                {
                    result  = LUB_HEAP_OK;
                    new_ptr = (char*)block->alloc.memory;
                    break;
                }
            }
        }
        if(words && (LUB_HEAP_FAILED == result))
        {
            /* need to reallocate and copy the data */
            new_ptr = lub_heap_new_alloc_block(this,words);
            if(NULL != new_ptr)
            {
                result = LUB_HEAP_OK;

                if(NULL != block)
                {
                    /* now copy the old contents across */
                    memcpy(new_ptr,
                           (const char*)block->alloc.memory,
                           (block->alloc.tag.words << 2) - sizeof(lub_heap_alloc_block_t));
                }
            }
            else
            {
                /* couldn't find the space for the request */
                break;
            }
        }
        /* now it's time to release the memory of the old block */
        if(NULL != block)
        {
            words_t old_words = block->alloc.tag.words;
            bool_t  done      = BOOL_FALSE;

            /* combine with the next block */
            if(LUB_HEAP_OK == lub_heap_merge_with_next(this,block))
            {
                done = BOOL_TRUE;
            }
            /* combine with the previous block */
            if(LUB_HEAP_OK == lub_heap_merge_with_previous(this,block))
            {
                done = BOOL_TRUE;
            }
            if(BOOL_FALSE == done)
            {
                /* create a new free block */
                lub_heap_new_free_block(this,block);
            }
            result = LUB_HEAP_OK;
            
            --this->stats.alloc_blocks;
            this->stats.alloc_bytes    -= (old_words << 2);
            this->stats.alloc_bytes    += sizeof(lub_heap_alloc_block_t);
            this->stats.alloc_overhead -= sizeof(lub_heap_alloc_block_t);
        }
    } while(0);

    if(LUB_HEAP_OK == result)
    {
        unsigned delta;
        
        /* align the block as required */
        if(LUB_HEAP_ALIGN_NATIVE != alignment)
        {
            lub_heap_align_block(this,
                                 alignment,
                                 &new_ptr,
                                 &size);
        }
        /* revert to client space available */
        size -= sizeof(lub_heap_alloc_block_t);
        *ptr = new_ptr;
        delta = (size - requested_size);
        
        if(*ptr && requested_size && (0 < delta))
        {
            /* make sure that any excess memory is tainted */
            lub_heap_taint_memory(*ptr + requested_size,LUB_HEAP_TAINT_ALLOC,delta);
        }
    }
    else if(   (LUB_HEAP_FAILED == result) 
            && (0               == requested_size)
            && (NULL            == *ptr))
    {
        /* freeing zero is always OK */
        result = LUB_HEAP_OK;
    }
    return result;
}
/*--------------------------------------------------------- */