[malloc] Add cache discard mechanism
[gpxe.git] / src / core / malloc.c
index bf4a8a3..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 <strings.h>
-#include <io.h>
+#include <gpxe/io.h>
 #include <gpxe/list.h>
-#include <malloc.h>
+#include <gpxe/init.h>
+#include <gpxe/malloc.h>
 
 /** @file
  *
@@ -49,9 +52,54 @@ struct autosized_block {
        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 *) )));
+
+/**
+ * Discard some cached data
+ *
+ * @ret discarded      Number of cached items discarded
+ */
+static unsigned int discard_cache ( void ) {
+       struct cache_discarder *discarder;
+       unsigned int discarded = 0;
+
+       for_each_table_entry ( discarder, CACHE_DISCARDERS ) {
+               discarded += discarder->discard();
+       }
+       return discarded;
+}
+
 /**
  * Allocate a memory block
  *
@@ -77,55 +125,64 @@ void * alloc_memblock ( size_t size, size_t align ) {
         */
        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 );
+       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;
                        }
-                       /* 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 );
-                       /* Zero allocated memory, for calloc() */
-                       memset ( block, 0, size );
-                       DBG ( "Allocated [%p,%p)\n", block,
-                             ( ( ( void * ) block ) + size ) );
-                       return block;
                }
-       }
 
-       DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
-       return NULL;
+               /* 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;
+               }
+       }
 }
 
 /**
@@ -190,6 +247,69 @@ void free_memblock ( void *ptr, size_t 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;
 }
 
 /**
@@ -202,21 +322,13 @@ void free_memblock ( void *ptr, size_t size ) {
  * will be aligned to at least a multiple of sizeof(void*).
  */
 void * malloc ( size_t size ) {
-       size_t total_size;
-       struct autosized_block *block;
-
-       total_size = size + offsetof ( struct autosized_block, data );
-       block = alloc_memblock ( total_size, 1 );
-       if ( ! block )
-               return NULL;
-       block->size = total_size;
-       return &block->data;
+       return realloc ( NULL, size );
 }
 
 /**
  * Free memory
  *
- * @v size             Memory allocated by malloc(), or NULL
+ * @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.
@@ -224,12 +336,27 @@ void * malloc ( size_t size ) {
  * If @c ptr is NULL, no action is taken.
  */
 void free ( void *ptr ) {
-       struct autosized_block *block;
+       realloc ( ptr, 0 );
+}
 
-       if ( ptr ) {
-               block = container_of ( ptr, struct autosized_block, data );
-               free_memblock ( block, block->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;
+
+       data = malloc ( size );
+       if ( data )
+               memset ( data, 0, size );
+       return data;
 }
 
 /**
@@ -250,8 +377,21 @@ void mpopulate ( void *start, size_t 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
  *