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

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