X-Git-Url: https://pd.if.org/git/?a=blobdiff_plain;f=functions%2Fstdlib%2Fmalloc.c;h=9cdd6895dfefd391b7be9a09ce04bf2f2c85e571;hb=b1fc26afebd4d557ff89a44bc21767a8704c3809;hp=a563350f929faf48c6949cdf59c1fe2c52031648;hpb=1d9d92ba957a0b8307c9a65c35867fde68e6533b;p=pdclib diff --git a/functions/stdlib/malloc.c b/functions/stdlib/malloc.c index a563350..9cdd689 100644 --- a/functions/stdlib/malloc.c +++ b/functions/stdlib/malloc.c @@ -1,121 +1,424 @@ -/* ---------------------------------------------------------------------------- - * $Id$ - * ---------------------------------------------------------------------------- - * Public Domain C Library - http://pdclib.sourceforge.net - * This code is Public Domain. Use, modify, and redistribute at will. - * --------------------------------------------------------------------------*/ +/* void * malloc( size_t ) -#include <__size_t.h> + This file is part of the Public Domain C Library (PDCLib). + Permission is granted to use, modify, and / or redistribute at will. +*/ -void * malloc( size_t size ) { /* TODO */ }; +#include +#include +#include -/* This is a simple best-fit / first-fit implementation heavily based on - * Thomas "Beyond Infinity" Kreitner's code - */ +#ifndef REGTEST -/* memory list element */ -struct chunk_t -{ - void * address; - size_t size; - chunk_t * next; -}; - -struct memlist_t -{ - chunk_t * start; - chunk_t * last; -}; +#include <_PDCLIB_glue.h> -size_t heap_start = 0xa0000000; -size_t heap_used = 0x00000050; /* HEAP in use. Holds the next FREE address (?) */ -size_t heap_max = 0xfffffff; /* max. HEAP */ +/* TODO: Primitive placeholder. Much room for improvement. */ -static struct memlist_t free_mem = { (struct memlist_t *) heap_start, - (struct memlist_t *) heap_start }; -/* free_mem.start->next = NULL; */ - -static struct memlist_t used_mem = { (struct memlist_t *) heap_start + sizeof( chunk_t ), - (struct memlist_t *) heap_start + sizeof( chunk_t ) }; -/* used_mem.start->next = NULL; */ +/* Keeping pointers to the first and the last element of the free list. */ +struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL }; void * malloc( size_t size ) { - chunk_t * chunk = 0; - chunk_t * prev_chunk; - if ( free_mem.start != free_mem.last ) + if ( size == 0 ) + { + return NULL; + } + if ( size < _PDCLIB_MINALLOC ) { - /* first pass: exact fit */ - chunk = free_mem.start; - while ( 1 ) + size = _PDCLIB_MINALLOC; + } + { + struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first; + struct _PDCLIB_memnode_t * previous = NULL; + struct _PDCLIB_memnode_t * firstfit = NULL; + struct _PDCLIB_memnode_t * firstfit_previous = NULL; + /* Trying exact fit */ + while ( current != NULL ) + { + if ( current->size == size ) { - prev_chunk = chunk; - chunk = chunk->next; - if ( ( chunk == NULL ) || ( chunk->size == size ) ) + /* Found exact fit, allocate node */ + if ( previous != NULL ) + { + /* Node in the middle of the list */ + previous->next = current->next; + } + else { - break; + /* Node is first in list */ + _PDCLIB_memlist.first = current->next; } + if ( _PDCLIB_memlist.last == current ) + { + /* Node is last in list */ + _PDCLIB_memlist.last = previous; + } + return (char *)current + sizeof( struct _PDCLIB_memnode_t ); + } + else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) ) + { + /* Remember previous node in case we do not get an exact fit. + Note that this is the node *pointing to* the first fit, + as we need that for allocating (i.e., changing next pointer). + */ + firstfit_previous = previous; + firstfit = current; } + /* Skip to next node */ + previous = current; + current = current->next; } - if ( chunk == NULL ) + /* No exact fit; go for first fit */ + if ( firstfit != NULL ) { - /* second pass - first fit */ - chunk = free_mem.start; - while ( 1 ) + bool node_split = false; + if ( ( firstfit->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) ) + { + /* Oversized - split into two nodes */ + struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size ); + newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t ); + newnode->next = firstfit->next; + firstfit->next = newnode; + firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t ); + node_split = true; + } + if ( firstfit_previous != NULL ) + { + /* Node in the middle of the list */ + firstfit_previous->next = firstfit->next; + } + else + { + /* Node is first in list */ + _PDCLIB_memlist.first = firstfit->next; + } + if ( _PDCLIB_memlist.last == firstfit ) { - prev_chunk = chunk; - chunk = chunk-> next; - if ( ( chunk == NULL ) || ( chunk->size > size ) ) + /* Node is last in list */ + if ( node_split ) { - break; + _PDCLIB_memlist.last = firstfit->next; + } + else + { + _PDCLIB_memlist.last = firstfit_previous; } } + return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ); + } } - if ( chunk != NULL ) { - /* remove chunk from free_mem list */ - if ( free_mem.start->next->next == NULL ) + /* No fit possible; how many additional pages do we need? */ + size_t pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1; + /* Allocate more pages */ + struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( (int)pages ); + if ( newnode != NULL ) + { + newnode->next = NULL; + newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t ); + if ( ( newnode->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) ) { - /* free_mem list has only one entry */ - free_mem.last = free_mem.start; + /* Oversized - split into two nodes */ + struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size ); + splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t ); + newnode->size = size; + /* Add splitted node as last element to free node list */ + if ( _PDCLIB_memlist.last == NULL ) + { + _PDCLIB_memlist.first = splitnode; + } + else + { + _PDCLIB_memlist.last->next = splitnode; + } + splitnode->next = NULL; /* TODO: This is bug #7, uncovered by testdriver yet. */ + _PDCLIB_memlist.last = splitnode; } - else if ( chunk == free_mem.last ) + return (char *)newnode + sizeof( struct _PDCLIB_memnode_t ); + } + } + /* No fit, heap extension not possible - out of memory */ + return NULL; +} + +#endif + + +#ifdef TEST +#include <_PDCLIB_test.h> +#include +#include +#include + + +#ifndef REGTEST + +/* Effective page size, i.e. how many bytes can be allocated and still be on + one page of memory. +*/ +#define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t ) +#define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr ) + +char * pages_start = 0; +int test_nodes( char const * const, int, ... ); +void PRINT( char const * const, ... ); + +/* This can be enabled to give a dump of node information */ +#if 0 +void PRINT( char const * const format, ... ) +{ + va_list( ap ); + va_start( ap, format ); + vprintf( format, ap ); +} +#else +void PRINT( char const * const format, ... ) +{ + /* EMPTY */ +} +#endif + +/* Helper function checking number of allocated memory pages and the nodes + in the free memory list against expectations. +*/ +int test_nodes( char const * const action, int expected_pages, ... ) +{ + static int count = 1; + int result = 1; + PRINT( action ); + /* Determining the amount of allocated pages */ + int allocated_pages = ( (intptr_t)_PDCLIB_allocpages( 0 ) - (intptr_t)pages_start ) / _PDCLIB_PAGESIZE; + PRINT( "Test #%2d, %d allocated pages", count++, allocated_pages ); + if ( allocated_pages != expected_pages ) + { + PRINT( " - MISMATCH, expected\n %d pages\n", expected_pages ); + result = 0; + } + else + { + PRINT( "\n" ); + } + /* Now moving through the free nodes list */ + va_list( ap ); + va_start( ap, expected_pages ); + struct _PDCLIB_memnode_t * tracer = _PDCLIB_memlist.first; + int firstnode = 0; + int lastnode = 0; + while ( tracer != NULL ) + { + /* Data from node */ + size_t node_location = (char *)tracer - (char *)pages_start; + PRINT( " - node %.4p, size %#.4x", node_location, tracer->size ); + /* Expected data */ + size_t expected_location = va_arg( ap, size_t ); + if ( expected_location == 0 ) { - /* chunk is last element of free_mem list */ - prev_chunk->next = NULL; - free_mem.last = prev_chunk; + PRINT( " - UNEXPECTED NODE\n" ); + result = 0; + continue; } - else + /* Memorizing first and last expected node for later comparison. */ + if ( firstnode == 0 ) { - /* chunk is neither only nor last in free_mem list */ - prev_chunk->next = prev_chunk->next->next; + firstnode = expected_location; } - /* append chunk to used_mem list */ - chunk->next = NULL; - used_mem.last->next = chunk; - used_mem.last = chunk; - } - /* append new chunk to end of used_mem list (if there's space) */ - if ( chunk == NULL ) - { - if ( ( heap_used + size ) <= heap_max ) + lastnode = expected_location; + /* Comparing expected node against current node */ + size_t expected_size = va_arg( ap, size_t ); + if ( ( node_location != expected_location ) || ( tracer->size != expected_size ) ) { - /* building the header */ - chunk = (chunk_t *) heap_start + heap_used + 1; - chunk->size = size; - chunk->next = NULL; - chunk->address = chunk + sizeof( chunk_t ); - /* push heap_used past allocated area */ - heap_used += sizeof( chunk_t ) + size; - used_mem.last->next = chunk; - used_mem.last = chunk; + PRINT( " - MISMATCH, expected values\n %.4p %#.4p\n", expected_location, expected_size ); + result = 0; } else { - /* allocation would exceed max. heap size - - /* demand more memory from kernel - not implemented */ - return 0; + PRINT( "\n" ); } + tracer = tracer->next; } - return (void *) chunk->address; + /* Comparing first and last node in memlist against expectations. */ + PRINT( " - memlist first: %#.4x - last: %#.4x", + ( _PDCLIB_memlist.first == NULL ) ? NULL : (char *)_PDCLIB_memlist.first - (char *)pages_start, + ( _PDCLIB_memlist.last == NULL ) ? NULL : (char *)_PDCLIB_memlist.last - (char *)pages_start ); + if ( ( firstnode != 0 ) && + ( ( ( (char *)_PDCLIB_memlist.first - (char *)pages_start ) != firstnode ) + || ( ( (char *)_PDCLIB_memlist.last - (char *)pages_start ) != lastnode ) ) ) + { + PRINT( " - MISMATCH, expected values\n %#.4x - last: %#.4x\n", firstnode, lastnode ); + result = 0; + } + else + { + PRINT( "\n" ); + } + PRINT( "\n" ); + return result; +} + +#endif + +/* Note that this test driver heavily tests *internals* of the implementation + above (and of free() and realloc(), too). That means that changes in the + implementation must be accompanied with appropriate changes of the test + driver. It does *not* make a good regression tester for the implementation, + I am afraid, and thus there is no REGTEST equivalent. +*/ + +int main( void ) +{ +#ifndef REGTEST + void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9, * ptrA, * ptrB, * ptrC; + + pages_start = _PDCLIB_allocpages( 0 ); + PRINT( "\nEffective is: %#.4x\nsizeof( memnode ) is: %#.2x\n\n", EFFECTIVE, sizeof( struct _PDCLIB_memnode_t ) ); + + /* Allocating 10 bytes; expecting one page allocation and a node split */ + TESTCASE( MEMTEST( ptr1, 10 ) ); + TESTCASE( test_nodes( "Allocating 10 bytes.", 1, + sizeof( struct _PDCLIB_memnode_t ) + 10, EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - 10, + 0 ) ); + + /* Allocating the rest of the page; expecting no page allocation and assignment of the remaining node */ + TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) ); + TESTCASE( test_nodes( "Allocating the rest of the page.", 1, + 0 ) ); + + /* Allocating a full page; expecting one page allocation, no node split */ + TESTCASE( MEMTEST( ptr3, EFFECTIVE ) ); + TESTCASE( test_nodes( "Allocating a full page.", 2, + 0 ) ); + + /* Allocating *almost* a full page; expecting one page allocation, no node split */ + TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) ); + TESTCASE( test_nodes( "Allocating *almost* a full page.", 3, + 0 ) ); + + /* Freeing and re-allocating the "almost" full page; expecting no page allocation, no node split */ + free( ptr4 ); + TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) ); + TESTCASE( ptr4 == ptr5 ); + TESTCASE( test_nodes( "Freeing and re-allocating the \"almost\" full page.", 3 ) ); + + /* Freeing the full page from test #3; expecting a full-sized free node. */ + free( ptr3 ); + TESTCASE( test_nodes( "Freeing the full page from test #3.", 3, + _PDCLIB_PAGESIZE * 1, EFFECTIVE, + 0 ) ); + + /* Allocating two full pages; expecting two page allocations, no node split */ + TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) ); + TESTCASE( test_nodes( "Allocating two full pages.", 5, + _PDCLIB_PAGESIZE * 1, EFFECTIVE, + 0 ) ); + + /* Re-allocating to size of 10 bytes; expecting no page allocation, no node split */ + /* TODO: Shouldn't realloc() split the now much-too-large node? */ + TESTCASE( realloc( ptr3, 10 ) == ptr3 ); + TESTCASE( test_nodes( "Re-allocating to size of 10 bytes.", 5, + _PDCLIB_PAGESIZE * 1, EFFECTIVE, + 0 ) ); + + /* Re-allocating to size of two full pages; expecting no page allocation, no node split */ + TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 ); + TESTCASE( test_nodes( "Re-allocating to size of two full pages.", 5, + _PDCLIB_PAGESIZE * 1, EFFECTIVE, + 0 ) ); + + /* Re-allocating to size of three full pages; expecting three page allocation, freeing of two-page node */ + TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 ); + TESTCASE( test_nodes( "Re-allocating to size of three full pages.", 8, + _PDCLIB_PAGESIZE * 1, EFFECTIVE, + _PDCLIB_PAGESIZE * 3, EFFECTIVE + _PDCLIB_PAGESIZE, + 0 ) ); + + /* Allocating two full pages; expecting allocation of the available two-page node */ + TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) ); + TESTCASE( test_nodes( "Allocating two full pages.", 8, + _PDCLIB_PAGESIZE * 1, EFFECTIVE, + 0 ) ); + + /* Allocating zero bytes; expecting no change */ + TESTCASE( ! MEMTEST( ptr6, 0 ) ); + TESTCASE( test_nodes( "Allocating zero bytes.", 8, + _PDCLIB_PAGESIZE * 1, EFFECTIVE, + 0 ) ); + + /* Allocating 4 bytes; expecting upsizing of requestupsizing of size, node split */ + TESTCASE( MEMTEST( ptr7, 4 ) ); + TESTCASE( test_nodes( "Allocating 4 bytes.", 8, + _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ), + EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ), + 0 ) ); + + /* Allocating the rest of the page; expecting no page allocation and assignment of the remaining node */ + TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) ); + TESTCASE( test_nodes( "Allocating the rest of the page.", 8, 0 ) ); + + /* Freeing the node from the previous test; expecting node to re-appear in free list */ + free( ptr8 ); + TESTCASE( test_nodes( "Freeing the node from the previous test.", 8, + _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ), + EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ), + 0 ) ); + + /* Allocating one byte more than available in free node; expecting page allocation */ + TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) ); + TESTCASE( test_nodes( "Allocating one byte more than available in free node.", 9, + _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ), + EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ), + 0 ) ); + + /* Re-allocating with NULL pointer; expecting no page allocation, no node split */ + ptr9 = realloc( NULL, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ); + TESTCASE( ptr9 != NULL ); + TESTCASE( memset( ptr9, 0, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) == ptr9 ); + TESTCASE( test_nodes( "Re-allocating with NULL pointer.", 9, 0 ) ); + + /* Allocating a bit more than half a page; expecting page allocation, node split */ +#define TESTSIZE 3000 + TESTCASE( MEMTEST( ptrA, TESTSIZE ) ); + TESTCASE( test_nodes( "Allocating a bit more than half a page.", 10, + _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + 0 ) ); + + /* Allocating a bit more than half a page; expecting page allocation, node split */ + TESTCASE( MEMTEST( ptrB, TESTSIZE ) ); + TESTCASE( test_nodes( "Allocating a bit more than half a page.", 11, + _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + 0 ) ); + + /* Allocating a bit more than half a page; expecting page allocation, node split */ + TESTCASE( MEMTEST( ptrC, TESTSIZE ) ); + TESTCASE( test_nodes( "Allocating a bit more than half a page.", 12, + _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + _PDCLIB_PAGESIZE * 11 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + 0 ) ); + + /* Freeing the middle node */ + free( ptrB ); + TESTCASE( test_nodes( "Freeing the middle node.", 12, + _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + _PDCLIB_PAGESIZE * 11 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE, + EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE, + _PDCLIB_PAGESIZE * 10, + TESTSIZE, + 0 ) ); + +#else + puts( " NOTEST malloc() test driver is PDCLib-specific." ); +#endif + return TEST_RESULTS; } + +#endif