[malloc] Add cache discard mechanism
[gpxe.git] / src / core / malloc.c
index db2b500..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
  *
@@ -69,6 +72,34 @@ struct autosized_block {
 /** 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
  *
@@ -96,52 +127,62 @@ void * alloc_memblock ( size_t size, size_t align ) {
        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 );
+       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 );
-                       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;
+               }
+       }
 }
 
 /**
@@ -206,6 +247,9 @@ void free_memblock ( void *ptr, size_t size ) {
                freeing->size += block->size;
                list_del ( &block->list );
        }
+
+       /* Update free memory counter */
+       freemem += size;
 }
 
 /**
@@ -302,8 +346,11 @@ void free ( void *ptr ) {
  * @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 * _calloc ( size_t size ) {
+void * zalloc ( size_t size ) {
        void *data;
 
        data = malloc ( size );
@@ -330,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
  *