pd.if.org Git - pdclib/blob - functions/stdlib/malloc.c

   1 /* $Id$ */
   2
   3 /* void * malloc( size_t )
   4
   5    This file is part of the Public Domain C Library (PDCLib).
   6    Permission is granted to use, modify, and / or redistribute at will.
   7 */
   8
   9 #include <stdlib.h>
  10 #include <stdint.h>
  11
  12 #ifndef REGTEST
  13
  14 #ifndef _PDCLIB_GLUE_H
  15 #define _PDCLIB_GLUE_H _PDLIB_GLUE_H
  16 #include <_PDCLIB_glue.h>
  17 #endif
  18
  19 /* TODO: Primitive placeholder. Much room for improvement. */
  20
  21 /* Keeping pointers to the first and the last element of the free list. */
  22 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
  23
  24 void * malloc( size_t size )
  25 {
  26     if ( size == 0 )
  27     {
  28         return NULL;
  29     }
  30     if ( size < _PDCLIB_MINALLOC )
  31     {
  32         size = _PDCLIB_MINALLOC;
  33     }
  34     {
  35     struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
  36     struct _PDCLIB_memnode_t * previous = NULL;
  37     struct _PDCLIB_memnode_t * firstfit = NULL;
  38     struct _PDCLIB_memnode_t * firstfit_previous = NULL;
  39     /* Trying exact fit */
  40     while ( current != NULL )
  41     {
  42         if ( current->size == size )
  43         {
  44             /* Found exact fit, allocate node */
  45             if ( previous != NULL )
  46             {
  47                 /* Node in the middle of the list */
  48                 previous->next = current->next;
  49             }
  50             else
  51             {
  52                 /* Node is first in list */
  53                 _PDCLIB_memlist.first = current->next;
  54             }
  55             if ( _PDCLIB_memlist.last == current )
  56             {
  57                 /* Node is last in list */
  58                 _PDCLIB_memlist.last = previous;
  59             }
  60             return (char *)current + sizeof( struct _PDCLIB_memnode_t );
  61         }
  62         else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
  63         {
  64             /* Remember previous node in case we do not get an exact fit.
  65                Note that this is the node *pointing to* the first fit,
  66                as we need that for allocating (i.e., changing next pointer).
  67             */
  68             firstfit_previous = previous;
  69             firstfit = current;
  70         }
  71         /* Skip to next node */
  72         previous = current;
  73         current = current->next;
  74     }
  75     /* No exact fit; go for first fit */
  76     if ( firstfit != NULL )
  77     {
  78         if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC )
  79         {
  80             /* Oversized - split into two nodes */
  81             struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
  82             newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
  83             newnode->next = firstfit->next;
  84             firstfit->next = newnode;
  85             firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
  86         }
  87         if ( firstfit_previous != NULL )
  88         {
  89             /* Node in the middle of the list */
  90             firstfit_previous->next = firstfit->next;
  91         }
  92         else
  93         {
  94             /* Node is first in list */
  95             _PDCLIB_memlist.first = firstfit->next;
  96         }
  97         if ( _PDCLIB_memlist.last == firstfit )
  98         {
  99             /* Node is last in list */
 100             _PDCLIB_memlist.last = firstfit_previous;
 101         }
 102         return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
 103     }
 104     }
 105     {
 106     /* No fit possible; how many additional pages do we need? */
 107     int pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
 108     /* Allocate more pages */
 109     struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( pages );
 110     if ( newnode != NULL )
 111     {
 112         newnode->next = NULL;
 113         newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
 114         if ( ( newnode->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
 115         {
 116             /* Oversized - split into two nodes */
 117             struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
 118             splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
 119             newnode->size = size;
 120             /* Add splitted node as last element to free node list */
 121             if ( _PDCLIB_memlist.last == NULL )
 122             {
 123                 _PDCLIB_memlist.first = splitnode;
 124             }
 125             else
 126             {
 127                 _PDCLIB_memlist.last->next = splitnode;
 128             }
 129             splitnode->next = NULL; /* TODO: This is bug #7, uncovered by testdriver yet. */
 130             _PDCLIB_memlist.last = splitnode;
 131         }
 132         return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
 133     }
 134     }
 135     /* No fit, heap extension not possible - out of memory */
 136     return NULL;
 137 }
 138
 139 #endif
 140
 141 #ifdef TEST
 142 #include <_PDCLIB_test.h>
 143 #include <string.h>
 144
 145 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
 146 #define PAGETEST( x ) ( pages_start + x * _PDCLIB_PAGESIZE ) == sbrk( 0 )
 147 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
 148
 149 /* This can be enabled to give a dump of available nodes */
 150 #if 0
 151 #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 )
 152 #else
 153 #define NODETRACE( x ) ( (void) 0 )
 154 #endif
 155
 156 /* Note that this test driver heavily tests *internals* of the implementation
 157    above (and of free() and realloc(), too). That means that changes in the
 158    implementation must be accompanied with appropriate changes of the test
 159    driver. It does *not* make a good regression tester for the implementation,
 160    I am afraid, and thus there is no REGTEST equivalent.
 161 */
 162
 163 void * sbrk( intptr_t );
 164
 165 int main( void )
 166 {
 167 #ifndef REGTEST
 168     void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9;
 169     char * pages_start = _PDCLIB_allocpages( 0 );
 170     /* allocating 10 byte; expected: 1 page allocation, node split */
 171     TESTCASE( MEMTEST( ptr1, 10 ) );
 172     TESTCASE( PAGETEST( 1 ) );
 173     NODETRACE( 1 );
 174     /* allocating EFFECTIVE - 10 byte; expected: no page allocation, receiving split node */
 175     TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
 176     TESTCASE( PAGETEST( 1 ) );
 177     NODETRACE( 2 );
 178     /* allocating EFFECTIVE; expected: 1 page allocation, no node split */
 179     TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
 180     TESTCASE( PAGETEST( 2 ) );
 181     NODETRACE( 3 );
 182     /* allocating EFFECTIVE - 4; expected: 1 page allocation, no node split */
 183     TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
 184     TESTCASE( PAGETEST( 3 ) );
 185     NODETRACE( 4 );
 186     /* freeing and re-allocating EFFECTIVE - 4; expected: no page allocation, no node split */
 187     free( ptr4 );
 188     TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
 189     TESTCASE( ptr4 == ptr5 );
 190     TESTCASE( PAGETEST( 3 ) );
 191     NODETRACE( 5 );
 192     /* releasing EFFECTIVE; expected: no page release */
 193     free( ptr3 );
 194     TESTCASE( PAGETEST( 3 ) );
 195     NODETRACE( 6 );
 196     /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: 2 page allocation, no node split */
 197     TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
 198     TESTCASE( PAGETEST( 5 ) );
 199     NODETRACE( 7 );
 200     /* reallocating to 10 byte; expected: no page allocation, no node split */
 201     TESTCASE( realloc( ptr3, 10 ) == ptr3 );
 202     TESTCASE( PAGETEST( 5 ) );
 203     NODETRACE( 8 );
 204     /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
 205     TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
 206     TESTCASE( PAGETEST( 5 ) );
 207     NODETRACE( 9 );
 208     /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE * 2; expected: 3 page allocations, no node split */
 209     TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
 210     TESTCASE( PAGETEST( 8 ) );
 211     NODETRACE( 10 );
 212     /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
 213     TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
 214     TESTCASE( PAGETEST( 8 ) );
 215     NODETRACE( 11 );
 216     /* allocating zero size; expected: no page allocation, no node split */
 217     TESTCASE( ! MEMTEST( ptr6, 0 ) );
 218     TESTCASE( PAGETEST( 8 ) );
 219     NODETRACE( 12 );
 220     /* allocating 4 byte; expected: no page allocation, upsizing of size, node split */
 221     TESTCASE( MEMTEST( ptr7, 4 ) );
 222     TESTCASE( PAGETEST( 8 ) );
 223     NODETRACE( 13 );
 224     /* allocating rest of page; expected: no page allocation, no node split */
 225     TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
 226     TESTCASE( PAGETEST( 8 ) );
 227     NODETRACE( 14 );
 228     /* freeing, and allocating one byte more; expected: 1 page allocation, no node split */
 229     free( ptr8 );
 230     NODETRACE( 15 );
 231     TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
 232     TESTCASE( PAGETEST( 9 ) );
 233     NODETRACE( 16 );
 234     /* realloc with NULL pointer; expected: no page allocation, no node split */
 235     ptr9 = realloc( NULL, 4072 );
 236     TESTCASE( ptr9 != NULL );
 237     TESTCASE( memset( ptr9, 0, 4072 ) == ptr9 );
 238     TESTCASE( PAGETEST( 9 ) );
 239     NODETRACE( 17 );
 240 #else
 241     puts( " NOTEST malloc() test driver is PDCLib-specific." );
 242 #endif
 243     return TEST_RESULTS;
 244 }
 245
 246 #endif