[malloc] Add cache discard mechanism
[gpxe.git] / src / core / malloc.c
index 8078406..61ea089 100644 (file)
  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  */
 
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <stddef.h>
 #include <stdint.h>
 #include <string.h>
-#include <io.h>
+#include <strings.h>
+#include <gpxe/io.h>
 #include <gpxe/list.h>
+#include <gpxe/init.h>
 #include <gpxe/malloc.h>
 
 /** @file
  *
- * Memory allocation
+ * Dynamic memory allocation
  *
  */
 
 /** A free block of memory */
-struct free_block {
+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;
+
 /**
- * Round size up to a memory allocation block size
+ * Heap size
  *
- * @v requested                Requested size
- * @ret obtained       Obtained size
+ * Currently fixed at 128kB.
+ */
+#define HEAP_SIZE ( 128 * 1024 )
+
+/** The heap itself */
+static char heap[HEAP_SIZE] __attribute__ (( aligned ( __alignof__(void *) )));
+
+/**
+ * Discard some cached data
  *
- * 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.
+ * @ret discarded      Number of cached items discarded
  */
-static size_t block_size ( size_t requested ) {
-       size_t obtained = 1;
+static unsigned int discard_cache ( void ) {
+       struct cache_discarder *discarder;
+       unsigned int discarded = 0;
 
-       while ( ( obtained < sizeof ( struct free_block ) ) ||
-               ( obtained < requested ) ) {
-               obtained <<= 1;
+       for_each_table_entry ( discarder, CACHE_DISCARDERS ) {
+               discarded += discarder->discard();
        }
-       return obtained;
+       return discarded;
 }
 
 /**
- * Allocate memory
+ * Allocate a memory block
  *
  * @v size             Requested size
- * @ret ptr            Allocated memory
+ * @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.
  *
- * 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.
+ * @c align must be a power of two.  @c size may not be zero.
  */
-void * gmalloc ( size_t size ) {
-       struct free_block *block;
-       struct free_block *buddy;
+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 block size to power of two */
-       size = block_size ( size );
+       /* 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 );
+       while ( 1 ) {
+               /* 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;
+                       }
+               }
 
-       /* Find the best available block */
+               /* Try discarding some cached data to free up memory */
+               if ( ! discard_cache() ) {
+                       /* Nothing available to discard */
+                       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 ) {
-               if ( block->size == size ) {
+               /* 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 );
-                       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 );
+                       freeing = block;
                }
+               /* Stop processing as soon as we reach a following block */
+               if ( gap_after >= 0 )
+                       break;
        }
 
-       /* Nothing available */
-       return NULL;
+       /* 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;
 }
 
 /**
- * Free memory
+ * 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.
  *
- * @v ptr              Allocated memory
- * @v size             Originally requested size
+ * If allocation fails the previously allocated block is left
+ * untouched and NULL is returned.
  *
- * Frees memory originally allocated by gmalloc().
+ * 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
  *
- * Calling gfree() with a NULL @c ptr is explicitly allowed, and
- * defined to have no effect.  Code such as
+ * @v size             Requested size
+ * @ret ptr            Memory, or NULL
  *
- * @code
+ * 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
  *
- * if ( ! my_ptr )
- *     gfree ( my_ptr, my_size )
+ * @v ptr              Memory allocated by malloc(), or NULL
  *
- * @endcode
+ * Memory allocated with malloc_dma() cannot be freed with free(); it
+ * must be freed with free_dma() instead.
  *
- * is perfectly valid, but should be avoided as unnecessary bloat.
+ * If @c ptr is NULL, no action is taken.
  */
-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;
+void free ( void *ptr ) {
+       realloc ( ptr, 0 );
+}
 
-       /* Round up block size to power of two */
-       size = block_size ( size );
-       freed_block->size = size;
+/**
+ * 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;
 
-       /* 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 );
+       data = malloc ( size );
+       if ( data )
+               memset ( data, 0, size );
+       return data;
 }
 
 /**
  * Add memory to allocation pool
  *
  * @v start            Start address
- * @v len              Length
+ * @v end              End address
  *
- * Adds a block of memory to the allocation pool.  This is a one-way
- * operation; there is no way to reclaim this memory.
+ * 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.
  *
- * There are no alignment requirements on either start or len.
+ * @c start must be aligned to at least a multiple of sizeof(void*).
  */
-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().
+void mpopulate ( void *start, size_t len ) {
+       /* Prevent free_memblock() from rounding up len beyond the end
+        * of what we were actually given...
         */
-       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;
-       }
+       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 <vsprintf.h>
+#include <stdio.h>
 /**
  * Dump free block list
  *
  */
-void gdumpfree ( void ) {
-       struct free_block *block;
+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,
+               printf ( "[%p,%p] (size %#zx)\n", block,
                         ( ( ( void * ) block ) + block->size ), block->size );
        }
 }