malloc.c

Go to the documentation of this file.

/*
 * Copyright (C) 2006 Michael Brown <mbrown@fensystems.co.uk>.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

FILE_LICENCE ( GPL2_OR_LATER );

#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <strings.h>
#include <gpxe/io.h>
#include <gpxe/list.h>
#include <gpxe/init.h>
#include <gpxe/malloc.h>

/** @file
 *
 * Dynamic memory allocation
 *
 */

/** A free block of memory */
struct memory_block {
        /** List of free blocks */
        struct list_head list;
        /** Size of this block */
        size_t size;
};

#define MIN_MEMBLOCK_SIZE \
        ( ( size_t ) ( 1 << ( fls ( sizeof ( struct memory_block ) - 1 ) ) ) )

/** A block of allocated memory complete with size information */
struct autosized_block {
        /** Size of this block */
        size_t size;
        /** Remaining data */
        char data[0];
};

/**
 * Address for zero-length memory blocks
 *
 * @c malloc(0) or @c realloc(ptr,0) will return the special value @c
 * NOWHERE.  Calling @c free(NOWHERE) will have no effect.
 *
 * This is consistent with the ANSI C standards, which state that
 * "either NULL or a pointer suitable to be passed to free()" must be
 * returned in these cases.  Using a special non-NULL value means that
 * the caller can take a NULL return value to indicate failure,
 * without first having to check for a requested size of zero.
 *
 * Code outside of malloc.c do not ever need to refer to the actual
 * value of @c NOWHERE; this is an internal definition.
 */
#define NOWHERE ( ( void * ) ~( ( intptr_t ) 0 ) )

/** List of free memory blocks */
static LIST_HEAD ( free_blocks );

/** Total amount of free memory */
size_t freemem;

/**
 * Heap size
 *
 * Currently fixed at 128kB.
 */
#define HEAP_SIZE ( 128 * 1024 )

/** The heap itself */
static char heap[HEAP_SIZE] __attribute__ (( aligned ( __alignof__(void *) )));

/**
 * Allocate a memory block
 *
 * @v size              Requested size
 * @v align             Physical alignment
 * @ret ptr             Memory block, or NULL
 *
 * Allocates a memory block @b physically aligned as requested.  No
 * guarantees are provided for the alignment of the virtual address.
 *
 * @c align must be a power of two.  @c size may not be zero.
 */
void * alloc_memblock ( size_t size, size_t align ) {
        struct memory_block *block;
        size_t align_mask;
        size_t pre_size;
        ssize_t post_size;
        struct memory_block *pre;
        struct memory_block *post;

        /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
         * calculate alignment mask.
         */
        size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
        align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );

        DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );

        /* Search through blocks for the first one with enough space */
        list_for_each_entry ( block, &free_blocks, list ) {
                pre_size = ( - virt_to_phys ( block ) ) & align_mask;
                post_size = block->size - pre_size - size;
                if ( post_size >= 0 ) {
                        /* Split block into pre-block, block, and
                         * post-block.  After this split, the "pre"
                         * block is the one currently linked into the
                         * free list.
                         */
                        pre   = block;
                        block = ( ( ( void * ) pre   ) + pre_size );
                        post  = ( ( ( void * ) block ) + size     );
                        DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
                              ( ( ( void * ) pre ) + pre->size ), pre, block,
                              post, ( ( ( void * ) pre ) + pre->size ) );
                        /* If there is a "post" block, add it in to
                         * the free list.  Leak it if it is too small
                         * (which can happen only at the very end of
                         * the heap).
                         */
                        if ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) {
                                post->size = post_size;
                                list_add ( &post->list, &pre->list );
                        }
                        /* Shrink "pre" block, leaving the main block
                         * isolated and no longer part of the free
                         * list.
                         */
                        pre->size = pre_size;
                        /* If there is no "pre" block, remove it from
                         * the list.  Also remove it (i.e. leak it) if
                         * it is too small, which can happen only at
                         * the very start of the heap.
                         */
                        if ( pre_size < MIN_MEMBLOCK_SIZE )
                                list_del ( &pre->list );
                        /* Update total free memory */
                        freemem -= size;
                        /* Return allocated block */
                        DBG ( "Allocated [%p,%p)\n", block,
                              ( ( ( void * ) block ) + size ) );
                        return block;
                }
        }

        DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
        return NULL;
}

/**
 * Free a memory block
 *
 * @v ptr               Memory allocated by alloc_memblock(), or NULL
 * @v size              Size of the memory
 *
 * If @c ptr is NULL, no action is taken.
 */
void free_memblock ( void *ptr, size_t size ) {
        struct memory_block *freeing;
        struct memory_block *block;
        ssize_t gap_before;
        ssize_t gap_after = -1;

        /* Allow for ptr==NULL */
        if ( ! ptr )
                return;

        /* Round up size to match actual size that alloc_memblock()
         * would have used.
         */
        size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
        freeing = ptr;
        freeing->size = size;
        DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));

        /* Insert/merge into free list */
        list_for_each_entry ( block, &free_blocks, list ) {
                /* Calculate gaps before and after the "freeing" block */
                gap_before = ( ( ( void * ) freeing ) - 
                               ( ( ( void * ) block ) + block->size ) );
                gap_after = ( ( ( void * ) block ) - 
                              ( ( ( void * ) freeing ) + freeing->size ) );
                /* Merge with immediately preceding block, if possible */
                if ( gap_before == 0 ) {
                        DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
                              ( ( ( void * ) block ) + block->size ), freeing,
                              ( ( ( void * ) freeing ) + freeing->size ),block,
                              ( ( ( void * ) freeing ) + freeing->size ) );
                        block->size += size;
                        list_del ( &block->list );
                        freeing = block;
                }
                /* Stop processing as soon as we reach a following block */
                if ( gap_after >= 0 )
                        break;
        }

        /* Insert before the immediately following block.  If
         * possible, merge the following block into the "freeing"
         * block.
         */
        DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
        list_add_tail ( &freeing->list, &block->list );
        if ( gap_after == 0 ) {
                DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
                      ( ( ( void * ) freeing ) + freeing->size ), block,
                      ( ( ( void * ) block ) + block->size ), freeing,
                      ( ( ( void * ) block ) + block->size ) );
                freeing->size += block->size;
                list_del ( &block->list );
        }

        /* Update free memory counter */
        freemem += size;
}

/**
 * Reallocate memory
 *
 * @v old_ptr           Memory previously allocated by malloc(), or NULL
 * @v new_size          Requested size
 * @ret new_ptr         Allocated memory, or NULL
 *
 * Allocates memory with no particular alignment requirement.  @c
 * new_ptr will be aligned to at least a multiple of sizeof(void*).
 * If @c old_ptr is non-NULL, then the contents of the newly allocated
 * memory will be the same as the contents of the previously allocated
 * memory, up to the minimum of the old and new sizes.  The old memory
 * will be freed.
 *
 * If allocation fails the previously allocated block is left
 * untouched and NULL is returned.
 *
 * Calling realloc() with a new size of zero is a valid way to free a
 * memory block.
 */
void * realloc ( void *old_ptr, size_t new_size ) {
        struct autosized_block *old_block;
        struct autosized_block *new_block;
        size_t old_total_size;
        size_t new_total_size;
        size_t old_size;
        void *new_ptr = NOWHERE;

        /* Allocate new memory if necessary.  If allocation fails,
         * return without touching the old block.
         */
        if ( new_size ) {
                new_total_size = ( new_size +
                                   offsetof ( struct autosized_block, data ) );
                new_block = alloc_memblock ( new_total_size, 1 );
                if ( ! new_block )
                        return NULL;
                new_block->size = new_total_size;
                new_ptr = &new_block->data;
        }
        
        /* Copy across relevant part of the old data region (if any),
         * then free it.  Note that at this point either (a) new_ptr
         * is valid, or (b) new_size is 0; either way, the memcpy() is
         * valid.
         */
        if ( old_ptr && ( old_ptr != NOWHERE ) ) {
                old_block = container_of ( old_ptr, struct autosized_block,
                                           data );
                old_total_size = old_block->size;
                old_size = ( old_total_size -
                             offsetof ( struct autosized_block, data ) );
                memcpy ( new_ptr, old_ptr,
                         ( ( old_size < new_size ) ? old_size : new_size ) );
                free_memblock ( old_block, old_total_size );
        }

        return new_ptr;
}

/**
 * Allocate memory
 *
 * @v size              Requested size
 * @ret ptr             Memory, or NULL
 *
 * Allocates memory with no particular alignment requirement.  @c ptr
 * will be aligned to at least a multiple of sizeof(void*).
 */
void * malloc ( size_t size ) {
        return realloc ( NULL, size );
}

/**
 * Free memory
 *
 * @v ptr               Memory allocated by malloc(), or NULL
 *
 * Memory allocated with malloc_dma() cannot be freed with free(); it
 * must be freed with free_dma() instead.
 *
 * If @c ptr is NULL, no action is taken.
 */
void free ( void *ptr ) {
        realloc ( ptr, 0 );
}

/**
 * Allocate cleared memory
 *
 * @v size              Requested size
 * @ret ptr             Allocated memory
 *
 * Allocate memory as per malloc(), and zero it.
 *
 * This function name is non-standard, but pretty intuitive.
 * zalloc(size) is always equivalent to calloc(1,size)
 */
void * zalloc ( size_t size ) {
        void *data;

        data = malloc ( size );
        if ( data )
                memset ( data, 0, size );
        return data;
}

/**
 * Add memory to allocation pool
 *
 * @v start             Start address
 * @v end               End address
 *
 * Adds a block of memory [start,end) to the allocation pool.  This is
 * a one-way operation; there is no way to reclaim this memory.
 *
 * @c start must be aligned to at least a multiple of sizeof(void*).
 */
void mpopulate ( void *start, size_t len ) {
        /* Prevent free_memblock() from rounding up len beyond the end
         * of what we were actually given...
         */
        free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
}

/**
 * Initialise the heap
 *
 */
static void init_heap ( void ) {
        mpopulate ( heap, sizeof ( heap ) );
}

/** Memory allocator initialisation function */
struct init_fn heap_init_fn __init_fn ( INIT_EARLY ) = {
        .initialise = init_heap,
};

#if 0
#include <stdio.h>
/**
 * Dump free block list
 *
 */
void mdumpfree ( void ) {
        struct memory_block *block;

        printf ( "Free block list:\n" );
        list_for_each_entry ( block, &free_blocks, list ) {
                printf ( "[%p,%p] (size %#zx)\n", block,
                         ( ( ( void * ) block ) + block->size ), block->size );
        }
}
#endif