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