X-Git-Url: https://pd.if.org/git/?a=blobdiff_plain;f=functions%2Fstdlib%2Fmalloc.c;h=22718ee67e778439d964d99d834201e878525f1e;hb=e6fd9753e785702792a00236f86f257a22f5c794;hp=a563350f929faf48c6949cdf59c1fe2c52031648;hpb=1d9d92ba957a0b8307c9a65c35867fde68e6533b;p=pdclib

diff --git a/functions/stdlib/malloc.c b/functions/stdlib/malloc.c
index a563350..22718ee 100644
--- a/functions/stdlib/malloc.c
+++ b/functions/stdlib/malloc.c
@@ -1,121 +1,246 @@
-/* ----------------------------------------------------------------------------
- * $Id$
- * ----------------------------------------------------------------------------
- * Public Domain C Library - http://pdclib.sourceforge.net
- * This code is Public Domain. Use, modify, and redistribute at will.
- * --------------------------------------------------------------------------*/
+/* $Id$ */
 
-#include <__size_t.h>
+/* void * malloc( size_t )
 
-void * malloc( size_t size ) { /* TODO */ };
+   This file is part of the Public Domain C Library (PDCLib).
+   Permission is granted to use, modify, and / or redistribute at will.
+*/
 
-/* This is a simple best-fit / first-fit implementation heavily based on
- * Thomas "Beyond Infinity" Kreitner's code
- */
+#include <stdlib.h>
+#include <stdint.h>
 
-/* memory list element */
-struct chunk_t
-{
-    void *    address;
-    size_t    size;
-    chunk_t * next;
-};
-
-struct memlist_t
-{
-    chunk_t * start;
-    chunk_t * last;
-};
+#ifndef REGTEST
 
-size_t heap_start = 0xa0000000;
-size_t heap_used  = 0x00000050; /* HEAP in use. Holds the next FREE address (?) */
-size_t heap_max   = 0xfffffff;  /* max. HEAP */
+#ifndef _PDCLIB_GLUE_H
+#define _PDCLIB_GLUE_H _PDLIB_GLUE_H
+#include <_PDCLIB_glue.h>
+#endif
 
-static struct memlist_t free_mem = { (struct memlist_t *) heap_start,
-                                     (struct memlist_t *) heap_start };
-/* free_mem.start->next = NULL; */
+/* TODO: Primitive placeholder. Much room for improvement. */
 
-static struct memlist_t used_mem = { (struct memlist_t *) heap_start + sizeof( chunk_t ),
-                                     (struct memlist_t *) heap_start + sizeof( chunk_t ) };
-/* used_mem.start->next = NULL; */
+/* Keeping pointers to the first and the last element of the free list. */
+struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
 
 void * malloc( size_t size )
 {
-    chunk_t * chunk = 0;
-    chunk_t * prev_chunk;
-    if ( free_mem.start != free_mem.last )
+    if ( size == 0 )
     {
-        /* first pass: exact fit */
-        chunk = free_mem.start;
-        while ( 1 )
-        {
-            prev_chunk = chunk;
-            chunk = chunk->next;
-            if ( ( chunk == NULL ) || ( chunk->size == size ) )
-            {
-                break;
-            }
-        }
+        return NULL;
     }
-    if ( chunk == NULL )
+    if ( size < _PDCLIB_MINALLOC )
+    {
+        size = _PDCLIB_MINALLOC;
+    }
+    {
+    struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
+    struct _PDCLIB_memnode_t * previous = NULL;
+    struct _PDCLIB_memnode_t * firstfit = NULL;
+    struct _PDCLIB_memnode_t * firstfit_previous = NULL;
+    /* Trying exact fit */
+    while ( current != NULL )
     {
-        /* second pass - first fit */
-        chunk = free_mem.start;
-        while ( 1 )
+        if ( current->size == size )
         {
-            prev_chunk = chunk;
-            chunk = chunk-> next;
-            if ( ( chunk == NULL ) || ( chunk->size > size ) )
+            /* Found exact fit, allocate node */
+            if ( previous != NULL )
             {
-                break;
+                /* Node in the middle of the list */
+                previous->next = current->next;
             }
+            else
+            {
+                /* Node is first in list */
+                _PDCLIB_memlist.first = current->next;
+            }
+            if ( _PDCLIB_memlist.last == current )
+            {
+                /* Node is last in list */
+                _PDCLIB_memlist.last = previous;
+            }
+            return (char *)current + sizeof( struct _PDCLIB_memnode_t );
         }
+        else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
+        {
+            /* Remember previous node in case we do not get an exact fit.
+               Note that this is the node *pointing to* the first fit,
+               as we need that for allocating (i.e., changing next pointer).
+            */
+            firstfit_previous = previous;
+            firstfit = current;
+        }
+        /* Skip to next node */
+        previous = current;
+        current = current->next;
     }
-    if ( chunk != NULL )
+    /* No exact fit; go for first fit */
+    if ( firstfit != NULL )
     {
-        /* remove chunk from free_mem list */
-        if ( free_mem.start->next->next == NULL )
+        if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC )
         {
-            /* free_mem list has only one entry */
-            free_mem.last = free_mem.start;
+            /* Oversized - split into two nodes */
+            struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
+            newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
+            newnode->next = firstfit->next;
+            firstfit->next = newnode;
+            firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
         }
-        else if ( chunk == free_mem.last )
+        if ( firstfit_previous != NULL )
         {
-            /* chunk is last element of free_mem list */
-            prev_chunk->next = NULL;
-            free_mem.last = prev_chunk;
+            /* Node in the middle of the list */
+            firstfit_previous->next = firstfit->next;
         }
         else
         {
-            /* chunk is neither only nor last in free_mem list */
-            prev_chunk->next = prev_chunk->next->next;
+            /* Node is first in list */
+            _PDCLIB_memlist.first = firstfit->next;
         }
-        /* append chunk to used_mem list */
-        chunk->next = NULL;
-        used_mem.last->next = chunk;
-        used_mem.last = chunk;
-    }
-    /* append new chunk to end of used_mem list (if there's space) */
-    if ( chunk == NULL )
-    {
-        if ( ( heap_used + size ) <= heap_max )
+        if ( _PDCLIB_memlist.last == firstfit )
         {
-            /* building the header */
-            chunk = (chunk_t *) heap_start + heap_used + 1;
-            chunk->size    = size;
-            chunk->next    = NULL;
-            chunk->address = chunk + sizeof( chunk_t );
-            /* push heap_used past allocated area */
-            heap_used += sizeof( chunk_t ) + size;
-            used_mem.last->next = chunk;
-            used_mem.last = chunk;
+            /* Node is last in list */
+            _PDCLIB_memlist.last = firstfit_previous;
         }
-        else
+        return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
+    }
+    }
+    {
+    /* No fit possible; how many additional pages do we need? */
+    int pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
+    /* Allocate more pages */
+    struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( pages );
+    if ( newnode != NULL )
+    {
+        newnode->next = NULL;
+        newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
+        if ( ( newnode->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
         {
-            /* allocation would exceed max. heap size -
-            /* demand more memory from kernel - not implemented */
-            return 0;
+            /* Oversized - split into two nodes */
+            struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
+            splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
+            newnode->size = size;
+            /* Add splitted node as last element to free node list */
+            if ( _PDCLIB_memlist.last == NULL )
+            {
+                _PDCLIB_memlist.first = splitnode;
+                splitnode->next = NULL;
+            }
+            else
+            {
+                _PDCLIB_memlist.last->next = splitnode;
+            }
+            _PDCLIB_memlist.last = splitnode;
         }
+        return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
     }
-    return (void *) chunk->address;
+    }
+    /* No fit, heap extension not possible - out of memory */
+    return NULL;
 }
+
+#endif
+
+#ifdef TEST
+#include <_PDCLIB_test.h>
+#include <string.h>
+
+#define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
+#define PAGETEST( x ) ( pages_start + x * _PDCLIB_PAGESIZE ) == sbrk( 0 )
+#define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
+
+/* This can be enabled to give a dump of available nodes */
+#if 0
+#define NODETRACE( x ) do { struct _PDCLIB_memnode_t * tracer = _PDCLIB_memlist.first; printf( "Node trace #%d, %d allocated pages\n", x, ( (intptr_t)sbrk( 0 ) - (intptr_t)pages_start ) / _PDCLIB_PAGESIZE ); while ( tracer != NULL ) { printf( "- node %p, size %#x\n", (void *)tracer, tracer->size ); tracer = tracer->next; } } while ( 0 )
+#else
+#define NODETRACE( x ) ( (void) 0 )
+#endif
+
+/* Note that this test driver heavily tests *internals* of the implementation
+   above (and of free() and realloc(), too). That means that changes in the
+   implementation must be accompanied with appropriate changes of the test
+   driver. It does *not* make a good regression tester for the implementation,
+   I am afraid, and thus there is no REGTEST equivalent.
+*/
+
+void * sbrk( intptr_t );
+
+int main( void )
+{
+#ifndef REGTEST
+    void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9;
+    char * pages_start = _PDCLIB_allocpages( 0 );
+    /* allocating 10 byte; expected: 1 page allocation, node split */
+    TESTCASE( MEMTEST( ptr1, 10 ) );
+    TESTCASE( PAGETEST( 1 ) );
+    NODETRACE( 1 );
+    /* allocating EFFECTIVE - 10 byte; expected: no page allocation, receiving split node */
+    TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
+    TESTCASE( PAGETEST( 1 ) );
+    NODETRACE( 2 );
+    /* allocating EFFECTIVE; expected: 1 page allocation, no node split */
+    TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
+    TESTCASE( PAGETEST( 2 ) );
+    NODETRACE( 3 );
+    /* allocating EFFECTIVE - 4; expected: 1 page allocation, no node split */
+    TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
+    TESTCASE( PAGETEST( 3 ) );
+    NODETRACE( 4 );
+    /* freeing and re-allocating EFFECTIVE - 4; expected: no page allocation, no node split */
+    free( ptr4 );
+    TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
+    TESTCASE( ptr4 == ptr5 );
+    TESTCASE( PAGETEST( 3 ) );
+    NODETRACE( 5 );
+    /* releasing EFFECTIVE; expected: no page release */
+    free( ptr3 );
+    TESTCASE( PAGETEST( 3 ) );
+    NODETRACE( 6 );
+    /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: 2 page allocation, no node split */
+    TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
+    TESTCASE( PAGETEST( 5 ) );
+    NODETRACE( 7 );
+    /* reallocating to 10 byte; expected: no page allocation, no node split */
+    TESTCASE( realloc( ptr3, 10 ) == ptr3 );
+    TESTCASE( PAGETEST( 5 ) );
+    NODETRACE( 8 );
+    /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
+    TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
+    TESTCASE( PAGETEST( 5 ) );
+    NODETRACE( 9 );
+    /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE * 2; expected: 3 page allocations, no node split */
+    TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
+    TESTCASE( PAGETEST( 8 ) );
+    NODETRACE( 10 );
+    /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
+    TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
+    TESTCASE( PAGETEST( 8 ) );
+    NODETRACE( 11 );
+    /* allocating zero size; expected: no page allocation, no node split */
+    TESTCASE( ! MEMTEST( ptr6, 0 ) );
+    TESTCASE( PAGETEST( 8 ) );
+    NODETRACE( 12 );
+    /* allocating 4 byte; expected: no page allocation, upsizing of size, node split */
+    TESTCASE( MEMTEST( ptr7, 4 ) );
+    TESTCASE( PAGETEST( 8 ) );
+    NODETRACE( 13 );
+    /* allocating rest of page; expected: no page allocation, no node split */
+    TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
+    TESTCASE( PAGETEST( 8 ) );
+    NODETRACE( 14 );
+    /* freeing, and allocating one byte more; expected: 1 page allocation, no node split */
+    free( ptr8 );
+    NODETRACE( 15 );
+    TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
+    TESTCASE( PAGETEST( 9 ) );
+    NODETRACE( 16 );
+    /* realloc with NULL pointer; expected: no page allocation, no node split */
+    ptr9 = realloc( NULL, 4072 );
+    TESTCASE( ptr9 != NULL );
+    TESTCASE( memset( ptr9, 0, 4072 ) == ptr9 );
+    TESTCASE( PAGETEST( 9 ) );
+    NODETRACE( 17 );
+#else
+    puts( "No testing of malloc() - test driver does not know internals of system function." );
+#endif
+    return TEST_RESULTS;
+}
+
+#endif