First draft of a dynamic memory allocator
authorMichael Brown <mcb30@etherboot.org>
Mon, 24 Apr 2006 15:21:18 +0000 (15:21 +0000)
committerMichael Brown <mcb30@etherboot.org>
Mon, 24 Apr 2006 15:21:18 +0000 (15:21 +0000)
src/core/malloc.c [new file with mode: 0644]
src/include/gpxe/malloc.h [new file with mode: 0644]

diff --git a/src/core/malloc.c b/src/core/malloc.c
new file mode 100644 (file)
index 0000000..8078406
--- /dev/null
@@ -0,0 +1,209 @@
+/*
+ * 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.
+ */
+
+#include <stdint.h>
+#include <string.h>
+#include <io.h>
+#include <gpxe/list.h>
+#include <gpxe/malloc.h>
+
+/** @file
+ *
+ * Memory allocation
+ *
+ */
+
+/** A free block of memory */
+struct free_block {
+       /** List of free blocks */
+       struct list_head list;
+       /** Size of this block */
+       size_t size;
+};
+
+/** List of free memory blocks */
+static LIST_HEAD ( free_blocks );
+
+/**
+ * Round size up to a memory allocation block size
+ *
+ * @v requested                Requested size
+ * @ret obtained       Obtained size
+ *
+ * The requested size is rounded up to the minimum allocation block
+ * size (the size of a struct @c free_block) and then rounded up to
+ * the nearest power of two.
+ */
+static size_t block_size ( size_t requested ) {
+       size_t obtained = 1;
+
+       while ( ( obtained < sizeof ( struct free_block ) ) ||
+               ( obtained < requested ) ) {
+               obtained <<= 1;
+       }
+       return obtained;
+}
+
+/**
+ * Allocate memory
+ *
+ * @v size             Requested size
+ * @ret ptr            Allocated memory
+ *
+ * gmalloc() will always allocate memory in power-of-two sized blocks,
+ * aligned to the corresponding power-of-two boundary.  For example, a
+ * request for 1500 bytes will return a 2048-byte block aligned to a
+ * 2048-byte boundary.
+ *
+ * The alignment applies to the physical address, not the virtual
+ * address.  The pointer value returned by gmalloc() therefore has no
+ * alignment guarantees, except as provided for by the
+ * virtual-to-physical mapping.  (In a PXE environment, this mapping
+ * is guaranteed to be a multiple of 16 bytes.)
+ *
+ * Unlike traditional malloc(), the caller must remember the size of
+ * the allocated block and pass the size to gfree().  This is done in
+ * order to allow efficient allocation of power-of-two sized and
+ * aligned blocks.
+ */
+void * gmalloc ( size_t size ) {
+       struct free_block *block;
+       struct free_block *buddy;
+
+       /* Round up block size to power of two */
+       size = block_size ( size );
+
+       /* Find the best available block */
+       list_for_each_entry ( block, &free_blocks, list ) {
+               if ( block->size == size ) {
+                       list_del ( &block->list );
+                       memset ( block, 0, size );
+                       return block;
+               }
+               while ( block->size > size ) {
+                       block->size >>= 1;
+                       buddy = ( ( ( void * ) block ) + block->size );
+                       buddy->size = block->size;
+                       list_add ( &buddy->list, &block->list );
+               }
+       }
+
+       /* Nothing available */
+       return NULL;
+}
+
+/**
+ * Free memory
+ *
+ * @v ptr              Allocated memory
+ * @v size             Originally requested size
+ *
+ * Frees memory originally allocated by gmalloc().
+ *
+ * Calling gfree() with a NULL @c ptr is explicitly allowed, and
+ * defined to have no effect.  Code such as
+ *
+ * @code
+ *
+ * if ( ! my_ptr )
+ *     gfree ( my_ptr, my_size )
+ *
+ * @endcode
+ *
+ * is perfectly valid, but should be avoided as unnecessary bloat.
+ */
+void gfree ( void *ptr, size_t size ) {
+       struct free_block *freed_block = ptr;
+       struct free_block *block;
+       
+       /* Cope with gfree(NULL,x) */
+       if ( ! ptr )
+               return;
+
+       /* Round up block size to power of two */
+       size = block_size ( size );
+       freed_block->size = size;
+
+       /* Merge back into free list */
+       list_for_each_entry ( block, &free_blocks, list ) {
+               if ( ( ( virt_to_phys ( block ) ^
+                        virt_to_phys ( freed_block ) ) == size ) &&
+                    ( block->size == size ) ) {
+                       list_del ( &block->list );
+                       size <<= 1;
+                       if ( block < freed_block )
+                               freed_block = block;
+                       freed_block->size = size;
+               } else if ( block->size > size ) {
+                       break;
+               }
+       }
+       list_add_tail ( &freed_block->list, &block->list );
+}
+
+/**
+ * Add memory to allocation pool
+ *
+ * @v start            Start address
+ * @v len              Length
+ *
+ * Adds a block of memory to the allocation pool.  This is a one-way
+ * operation; there is no way to reclaim this memory.
+ *
+ * There are no alignment requirements on either start or len.
+ */
+void gmpopulate ( void *start, size_t len ) {
+       size_t frag_len;
+
+       /* Split region into power-of-two sized and aligned blocks,
+        * and feed them to gfree().
+        */
+       while ( len ) {
+               frag_len = 1;
+               /* Find maximum allowed alignment for this address */
+               while ( ( virt_to_phys ( start ) & frag_len ) == 0 ) { 
+                       frag_len <<= 1;
+               }
+               /* Find maximum block size that fits in remaining space */
+               while ( frag_len > len ) {
+                       frag_len >>= 1;
+               }
+               /* Skip blocks that are too small */
+               if ( frag_len >= sizeof ( struct free_block ) )
+                       gfree ( start, frag_len );
+               start += frag_len;
+               len -= frag_len;
+       }
+}
+
+#if 0
+#include <vsprintf.h>
+/**
+ * Dump free block list
+ *
+ */
+void gdumpfree ( void ) {
+       struct free_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
diff --git a/src/include/gpxe/malloc.h b/src/include/gpxe/malloc.h
new file mode 100644 (file)
index 0000000..abb0008
--- /dev/null
@@ -0,0 +1,36 @@
+#ifndef _GPXE_MALLOC_H
+#define _GPXE_MALLOC_H
+
+#include <stdint.h>
+
+/** @file
+ *
+ * Memory allocation
+ *
+ */
+
+extern void * gmalloc ( size_t size );
+extern void gfree ( void *ptr, size_t size );
+extern void gmpopulate ( void *start, size_t len );
+
+/**
+ * Allocate cleared memory
+ *
+ * @v size             Requested size
+ * @ret ptr            Allocated memory
+ *
+ * Allocate memory as per gmalloc(), and zero it.
+ *
+ * Note that gmalloc() and gcalloc() are identical, in the interests
+ * of reducing code size.  Callers should not, however, rely on
+ * gmalloc() clearing memory, since this behaviour may change in
+ * future.
+ */
+static inline void * gcalloc ( size_t size ) {
+       return gmalloc ( size );
+}
+
+/* Debug function; not compiled in by default */
+void gdumpfree ( void );
+
+#endif /* _GPXE_MALLOC_H */