pd.if.org Git - pdclib/blob - opt/malloc-solar/malloc.c

   1 /* void * malloc( size_t )
   2
   3    This file is part of the Public Domain C Library (PDCLib).
   4    Permission is granted to use, modify, and / or redistribute at will.
   5 */
   6
   7 #include <stdlib.h>
   8 #include <stdint.h>
   9 #include <stdbool.h>
  10
  11 #ifndef REGTEST
  12 #include <_PDCLIB_glue.h>
  13
  14 /* TODO: Primitive placeholder. Much room for improvement. */
  15
  16 /* Keeping pointers to the first and the last element of the free list. */
  17 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
  18
  19 void * malloc( size_t size )
  20 {
  21     if ( size == 0 )
  22     {
  23         return NULL;
  24     }
  25     if ( size < _PDCLIB_MINALLOC )
  26     {
  27         size = _PDCLIB_MINALLOC;
  28     }
  29     {
  30     struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
  31     struct _PDCLIB_memnode_t * previous = NULL;
  32     struct _PDCLIB_memnode_t * firstfit = NULL;
  33     struct _PDCLIB_memnode_t * firstfit_previous = NULL;
  34     /* Trying exact fit */
  35     while ( current != NULL )
  36     {
  37         if ( current->size == size )
  38         {
  39             /* Found exact fit, allocate node */
  40             if ( previous != NULL )
  41             {
  42                 /* Node in the middle of the list */
  43                 previous->next = current->next;
  44             }
  45             else
  46             {
  47                 /* Node is first in list */
  48                 _PDCLIB_memlist.first = current->next;
  49             }
  50             if ( _PDCLIB_memlist.last == current )
  51             {
  52                 /* Node is last in list */
  53                 _PDCLIB_memlist.last = previous;
  54             }
  55             return (char *)current + sizeof( struct _PDCLIB_memnode_t );
  56         }
  57         else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
  58         {
  59             /* Remember previous node in case we do not get an exact fit.
  60                Note that this is the node *pointing to* the first fit,
  61                as we need that for allocating (i.e., changing next pointer).
  62             */
  63             firstfit_previous = previous;
  64             firstfit = current;
  65         }
  66         /* Skip to next node */
  67         previous = current;
  68         current = current->next;
  69     }
  70     /* No exact fit; go for first fit */
  71     if ( firstfit != NULL )
  72     {
  73         bool node_split = false;
  74         if ( ( firstfit->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
  75         {
  76             /* Oversized - split into two nodes */
  77             struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
  78             newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
  79             newnode->next = firstfit->next;
  80             firstfit->next = newnode;
  81             firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
  82             node_split = true;
  83         }
  84         if ( firstfit_previous != NULL )
  85         {
  86             /* Node in the middle of the list */
  87             firstfit_previous->next = firstfit->next;
  88         }
  89         else
  90         {
  91             /* Node is first in list */
  92             _PDCLIB_memlist.first = firstfit->next;
  93         }
  94         if ( _PDCLIB_memlist.last == firstfit )
  95         {
  96             /* Node is last in list */
  97             if ( node_split )
  98             {
  99                 _PDCLIB_memlist.last = firstfit->next;
 100             }
 101             else
 102             {
 103                 _PDCLIB_memlist.last = firstfit_previous;
 104             }
 105         }
 106         return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
 107     }
 108     }
 109     {
 110     /* No fit possible; how many additional pages do we need? */
 111     size_t pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
 112     /* Allocate more pages */
 113     struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( (int)pages );
 114     if ( newnode != NULL )
 115     {
 116         newnode->next = NULL;
 117         newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
 118         if ( ( newnode->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
 119         {
 120             /* Oversized - split into two nodes */
 121             struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
 122             splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
 123             newnode->size = size;
 124             /* Add splitted node as last element to free node list */
 125             if ( _PDCLIB_memlist.last == NULL )
 126             {
 127                 _PDCLIB_memlist.first = splitnode;
 128             }
 129             else
 130             {
 131                 _PDCLIB_memlist.last->next = splitnode;
 132             }
 133             splitnode->next = NULL; /* TODO: This is bug #7, uncovered by testdriver yet. */
 134             _PDCLIB_memlist.last = splitnode;
 135         }
 136         return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
 137     }
 138     }
 139     /* No fit, heap extension not possible - out of memory */
 140     return NULL;
 141 }
 142
 143 #endif
 144
 145
 146 #ifdef TEST
 147 #include <_PDCLIB_test.h>
 148 #include <string.h>
 149 #include <stdarg.h>
 150 #include <stdio.h>
 151
 152
 153 #ifndef REGTEST
 154
 155 /* Effective page size, i.e. how many bytes can be allocated and still be on
 156    one page of memory.
 157 */
 158 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
 159 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
 160
 161 char * pages_start = 0;
 162 int test_nodes( char const * const, int, ... );
 163 void PRINT( char const * const, ... );
 164
 165 /* This can be enabled to give a dump of node information */
 166 #if 0
 167 void PRINT( char const * const format, ... )
 168 {
 169     va_list( ap );
 170     va_start( ap, format );
 171     vprintf( format, ap );
 172 }
 173 #else
 174 void PRINT( char const * const format, ... )
 175 {
 176     /* EMPTY */
 177 }
 178 #endif
 179
 180 /* Helper function checking number of allocated memory pages and the nodes
 181    in the free memory list against expectations.
 182 */
 183 int test_nodes( char const * const action, int expected_pages, ... )
 184 {
 185     static int count = 1;
 186     int result = 1;
 187     PRINT( action );
 188     /* Determining the amount of allocated pages */
 189     int allocated_pages = ( (intptr_t)_PDCLIB_allocpages( 0 ) - (intptr_t)pages_start ) / _PDCLIB_PAGESIZE;
 190     PRINT( "Test #%2d, %d allocated pages", count++, allocated_pages );
 191     if ( allocated_pages != expected_pages )
 192     {
 193         PRINT( " - MISMATCH, expected\n          %d pages\n", expected_pages );
 194         result = 0;
 195     }
 196     else
 197     {
 198         PRINT( "\n" );
 199     }
 200     /* Now moving through the free nodes list */
 201     va_list( ap );
 202     va_start( ap, expected_pages );
 203     struct _PDCLIB_memnode_t * tracer = _PDCLIB_memlist.first;
 204     int firstnode = 0;
 205     int lastnode = 0;
 206     while ( tracer != NULL )
 207     {
 208         /* Data from node */
 209         size_t node_location = (char *)tracer - (char *)pages_start;
 210         PRINT( "   - node %.4p, size %#.4x", node_location, tracer->size );
 211         /* Expected data */
 212         size_t expected_location = va_arg( ap, size_t );
 213         if ( expected_location == 0 )
 214         {
 215             PRINT( " - UNEXPECTED NODE\n" );
 216             result = 0;
 217             continue;
 218         }
 219         /* Memorizing first and last expected node for later comparison. */
 220         if ( firstnode == 0 )
 221         {
 222             firstnode = expected_location;
 223         }
 224         lastnode = expected_location;
 225         /* Comparing expected node against current node */
 226         size_t expected_size = va_arg( ap, size_t );
 227         if ( ( node_location != expected_location ) || ( tracer->size != expected_size ) )
 228         {
 229             PRINT( " - MISMATCH, expected values\n          %.4p       %#.4p\n", expected_location, expected_size );
 230             result = 0;
 231         }
 232         else
 233         {
 234             PRINT( "\n" );
 235         }
 236         tracer = tracer->next;
 237     }
 238     /* Comparing first and last node in memlist against expectations. */
 239     PRINT( "   - memlist first: %#.4x - last: %#.4x",
 240             ( _PDCLIB_memlist.first == NULL ) ? NULL : (char *)_PDCLIB_memlist.first - (char *)pages_start,
 241             ( _PDCLIB_memlist.last == NULL ) ? NULL : (char *)_PDCLIB_memlist.last - (char *)pages_start );
 242     if ( ( firstnode != 0 ) &&
 243          ( ( ( (char *)_PDCLIB_memlist.first - (char *)pages_start ) != firstnode )
 244          || ( ( (char *)_PDCLIB_memlist.last  - (char *)pages_start ) != lastnode ) ) )
 245     {
 246         PRINT( " - MISMATCH, expected values\n                    %#.4x - last: %#.4x\n", firstnode, lastnode );
 247         result = 0;
 248     }
 249     else
 250     {
 251         PRINT( "\n" );
 252     }
 253     PRINT( "\n" );
 254     return result;
 255 }
 256
 257 #endif
 258
 259 /* Note that this test driver heavily tests *internals* of the implementation
 260    above (and of free() and realloc(), too). That means that changes in the
 261    implementation must be accompanied with appropriate changes of the test
 262    driver. It does *not* make a good regression tester for the implementation,
 263    I am afraid, and thus there is no REGTEST equivalent.
 264 */
 265
 266 int main( void )
 267 {
 268 #ifndef REGTEST
 269     void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9, * ptrA, * ptrB, * ptrC;
 270
 271     pages_start = _PDCLIB_allocpages( 0 );
 272     PRINT( "\nEffective is: %#.4x\nsizeof( memnode ) is: %#.2x\n\n", EFFECTIVE, sizeof( struct _PDCLIB_memnode_t ) );
 273
 274     /* Allocating 10 bytes; expecting one page allocation and a node split */
 275     TESTCASE( MEMTEST( ptr1, 10 ) );
 276     TESTCASE( test_nodes( "Allocating 10 bytes.", 1,
 277                sizeof( struct _PDCLIB_memnode_t ) + 10, EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - 10,
 278                0 ) );
 279
 280     /* Allocating the rest of the page; expecting no page allocation and assignment of the remaining node */
 281     TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
 282     TESTCASE( test_nodes( "Allocating the rest of the page.", 1,
 283                0 ) );
 284
 285     /* Allocating a full page; expecting one page allocation, no node split */
 286     TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
 287     TESTCASE( test_nodes( "Allocating a full page.", 2,
 288                0 ) );
 289
 290     /* Allocating *almost* a full page; expecting one page allocation, no node split */
 291     TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
 292     TESTCASE( test_nodes( "Allocating *almost* a full page.", 3,
 293                0 ) );
 294
 295     /* Freeing and re-allocating the "almost" full page; expecting no page allocation, no node split */
 296     free( ptr4 );
 297     TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
 298     TESTCASE( ptr4 == ptr5 );
 299     TESTCASE( test_nodes( "Freeing and re-allocating the \"almost\" full page.", 3 ) );
 300
 301     /* Freeing the full page from test #3; expecting a full-sized free node. */
 302     free( ptr3 );
 303     TESTCASE( test_nodes( "Freeing the full page from test #3.", 3,
 304                _PDCLIB_PAGESIZE * 1, EFFECTIVE,
 305                0 ) );
 306
 307     /* Allocating two full pages; expecting two page allocations, no node split */
 308     TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
 309     TESTCASE( test_nodes( "Allocating two full pages.", 5,
 310                _PDCLIB_PAGESIZE * 1, EFFECTIVE,
 311                0 ) );
 312
 313     /* Re-allocating to size of 10 bytes; expecting no page allocation, no node split */
 314     /* TODO: Shouldn't realloc() split the now much-too-large node? */
 315     TESTCASE( realloc( ptr3, 10 ) == ptr3 );
 316     TESTCASE( test_nodes( "Re-allocating to size of 10 bytes.", 5,
 317                _PDCLIB_PAGESIZE * 1, EFFECTIVE,
 318                0 ) );
 319
 320     /* Re-allocating to size of two full pages; expecting no page allocation, no node split */
 321     TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
 322     TESTCASE( test_nodes( "Re-allocating to size of two full pages.", 5,
 323                _PDCLIB_PAGESIZE * 1, EFFECTIVE,
 324                0 ) );
 325
 326     /* Re-allocating to size of three full pages; expecting three page allocation, freeing of two-page node */
 327     TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
 328     TESTCASE( test_nodes( "Re-allocating to size of three full pages.", 8,
 329                _PDCLIB_PAGESIZE * 1, EFFECTIVE,
 330                _PDCLIB_PAGESIZE * 3, EFFECTIVE + _PDCLIB_PAGESIZE,
 331                0 ) );
 332
 333     /* Allocating two full pages; expecting allocation of the available two-page node */
 334     TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
 335     TESTCASE( test_nodes( "Allocating two full pages.", 8,
 336                _PDCLIB_PAGESIZE * 1, EFFECTIVE,
 337                0 ) );
 338
 339     /* Allocating zero bytes; expecting no change */
 340     TESTCASE( ! MEMTEST( ptr6, 0 ) );
 341     TESTCASE( test_nodes( "Allocating zero bytes.", 8,
 342                _PDCLIB_PAGESIZE * 1, EFFECTIVE,
 343                0 ) );
 344
 345     /* Allocating 4 bytes; expecting upsizing of requestupsizing of size, node split */
 346     TESTCASE( MEMTEST( ptr7, 4 ) );
 347     TESTCASE( test_nodes( "Allocating 4 bytes.", 8,
 348                _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
 349                EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
 350                0 ) );
 351
 352     /* Allocating the rest of the page; expecting no page allocation and assignment of the remaining node */
 353     TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
 354     TESTCASE( test_nodes( "Allocating the rest of the page.", 8, 0 ) );
 355
 356     /* Freeing the node from the previous test; expecting node to re-appear in free list */
 357     free( ptr8 );
 358     TESTCASE( test_nodes( "Freeing the node from the previous test.", 8,
 359                _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
 360                EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
 361                0 ) );
 362
 363     /* Allocating one byte more than available in free node; expecting page allocation */
 364     TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
 365     TESTCASE( test_nodes( "Allocating one byte more than available in free node.", 9,
 366                _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
 367                EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
 368                0 ) );
 369
 370     /* Re-allocating with NULL pointer; expecting no page allocation, no node split */
 371     ptr9 = realloc( NULL, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) );
 372     TESTCASE( ptr9 != NULL );
 373     TESTCASE( memset( ptr9, 0, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) == ptr9 );
 374     TESTCASE( test_nodes( "Re-allocating with NULL pointer.", 9, 0 ) );
 375
 376     /* Allocating a bit more than half a page; expecting page allocation, node split */
 377 #define TESTSIZE 3000
 378     TESTCASE( MEMTEST( ptrA, TESTSIZE ) );
 379     TESTCASE( test_nodes( "Allocating a bit more than half a page.", 10,
 380                _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 381                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 382                0 ) );
 383
 384     /* Allocating a bit more than half a page; expecting page allocation, node split */
 385     TESTCASE( MEMTEST( ptrB, TESTSIZE ) );
 386     TESTCASE( test_nodes( "Allocating a bit more than half a page.", 11,
 387                _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 388                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 389                _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 390                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 391                0 ) );
 392
 393     /* Allocating a bit more than half a page; expecting page allocation, node split */
 394     TESTCASE( MEMTEST( ptrC, TESTSIZE ) );
 395     TESTCASE( test_nodes( "Allocating a bit more than half a page.", 12,
 396                _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 397                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 398                _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 399                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 400                _PDCLIB_PAGESIZE * 11 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 401                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 402                0 ) );
 403
 404     /* Freeing the middle node */
 405     free( ptrB );
 406     TESTCASE( test_nodes( "Freeing the middle node.", 12,
 407                _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 408                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 409                _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 410                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 411                _PDCLIB_PAGESIZE * 11 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
 412                EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
 413                _PDCLIB_PAGESIZE * 10,
 414                TESTSIZE,
 415                0 ) );
 416
 417 #else
 418     puts( " NOTEST malloc() test driver is PDCLib-specific." );
 419 #endif
 420     return TEST_RESULTS;
 421 }
 422
 423 #endif