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