1 files changed, 386 insertions, 0 deletions
diff --git a/contrib/syslinux-4.02/gpxe/src/core/malloc.c b/contrib/syslinux-4.02/gpxe/src/core/malloc.c
new file mode 100644
index 0000000..0153748
--- /dev/null
+++ b/contrib/syslinux-4.02/gpxe/src/core/malloc.c
@@ -0,0 +1,386 @@
+/*
+ * 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 512kB.
+ */
+#define HEAP_SIZE ( 512 * 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