pd.if.org Git - pdclib.old/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                 splitnode->next = NULL;
 125             }
 126             else
 127             {
 128                 _PDCLIB_memlist.last->next = splitnode;
 129             }
 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     printf( "Start of malloc() testing...\n" );
 169     {
 170     void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9;
 171     char * pages_start = _PDCLIB_allocpages( 0 );
 172     /* allocating 10 byte; expected: 1 page allocation, node split */
 173     TESTCASE( MEMTEST( ptr1, 10 ) );
 174     TESTCASE( PAGETEST( 1 ) );
 175     NODETRACE( 1 );
 176     /* allocating EFFECTIVE - 10 byte; expected: no page allocation, receiving split node */
 177     TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
 178     TESTCASE( PAGETEST( 1 ) );
 179     NODETRACE( 2 );
 180     /* allocating EFFECTIVE; expected: 1 page allocation, no node split */
 181     TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
 182     TESTCASE( PAGETEST( 2 ) );
 183     NODETRACE( 3 );
 184     /* allocating EFFECTIVE - 4; expected: 1 page allocation, no node split */
 185     TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
 186     TESTCASE( PAGETEST( 3 ) );
 187     NODETRACE( 4 );
 188     /* freeing and re-allocating EFFECTIVE - 4; expected: no page allocation, no node split */
 189     free( ptr4 );
 190     TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
 191     TESTCASE( ptr4 == ptr5 );
 192     TESTCASE( PAGETEST( 3 ) );
 193     NODETRACE( 5 );
 194     /* releasing EFFECTIVE; expected: no page release */
 195     free( ptr3 );
 196     TESTCASE( PAGETEST( 3 ) );
 197     NODETRACE( 6 );
 198     /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: 2 page allocation, no node split */
 199     TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
 200     TESTCASE( PAGETEST( 5 ) );
 201     NODETRACE( 7 );
 202     /* reallocating to 10 byte; expected: no page allocation, no node split */
 203     TESTCASE( realloc( ptr3, 10 ) == ptr3 );
 204     TESTCASE( PAGETEST( 5 ) );
 205     NODETRACE( 8 );
 206     /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
 207     TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
 208     TESTCASE( PAGETEST( 5 ) );
 209     NODETRACE( 9 );
 210     /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE * 2; expected: 3 page allocations, no node split */
 211     TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
 212     TESTCASE( PAGETEST( 8 ) );
 213     NODETRACE( 10 );
 214     /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */
 215     TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
 216     TESTCASE( PAGETEST( 8 ) );
 217     NODETRACE( 11 );
 218     /* allocating zero size; expected: no page allocation, no node split */
 219     TESTCASE( ! MEMTEST( ptr6, 0 ) );
 220     TESTCASE( PAGETEST( 8 ) );
 221     NODETRACE( 12 );
 222     /* allocating 4 byte; expected: no page allocation, upsizing of size, node split */
 223     TESTCASE( MEMTEST( ptr7, 4 ) );
 224     TESTCASE( PAGETEST( 8 ) );
 225     NODETRACE( 13 );
 226     /* allocating rest of page; expected: no page allocation, no node split */
 227     TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
 228     TESTCASE( PAGETEST( 8 ) );
 229     NODETRACE( 14 );
 230     /* freeing, and allocating one byte more; expected: 1 page allocation, no node split */
 231     free( ptr8 );
 232     NODETRACE( 15 );
 233     TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
 234     TESTCASE( PAGETEST( 9 ) );
 235     NODETRACE( 16 );
 236     /* realloc with NULL pointer; expected: no page allocation, no node split */
 237     ptr9 = realloc( NULL, 4072 );
 238     TESTCASE( ptr9 != NULL );
 239     TESTCASE( memset( ptr9, 0, 4072 ) == ptr9 );
 240     TESTCASE( PAGETEST( 9 ) );
 241     NODETRACE( 17 );
 242     printf( "End of malloc() testing.\n" );
 243     }
 244 #else
 245     puts( "No testing of malloc() - test driver does not know internals of system function." );
 246 #endif
 247     return TEST_RESULTS;
 248 }
 249
 250 #endif