From: solar Date: Mon, 6 Feb 2006 21:07:38 +0000 (+0000) Subject: Adding malloc(), free(), and realloc(). X-Git-Tag: v0.4~1 X-Git-Url: https://pd.if.org/git/?p=pdclib;a=commitdiff_plain;h=137bef7f4838fc430682213fa628e16b2237ed63 Adding malloc(), free(), and realloc(). --- diff --git a/functions/stdlib/free.c b/functions/stdlib/free.c new file mode 100644 index 0000000..632f670 --- /dev/null +++ b/functions/stdlib/free.c @@ -0,0 +1,52 @@ +/* $Id$ */ + +/* Release $Name$ */ + +/* void free( void * ) + + This file is part of the Public Domain C Library (PDCLib). + Permission is granted to use, modify, and / or redistribute at will. +*/ + +#include + +#ifndef REGTEST + +#ifndef _PDCLIB_INT_H +#define _PDCLIB_INT_H _PDCLIB_INT_H +#include <_PDCLIB_int.h> +#endif + +/* TODO: Primitive placeholder. Much room for improvement. */ + +/* structure holding first and last element of free node list */ +extern struct _PDCLIB_headnode_t _PDCLIB_memlist; + +void free( void * ptr ) +{ + ptr = (void *)( (char *)ptr - sizeof( struct _PDCLIB_memnode_t ) ); + ( (struct _PDCLIB_memnode_t *)ptr )->next = NULL; + if ( _PDCLIB_memlist.last != NULL ) + { + _PDCLIB_memlist.last->next = ptr; + } + else + { + _PDCLIB_memlist.first = ptr; + } + _PDCLIB_memlist.last = ptr; +} + +#endif + +#ifdef TEST +#include <_PDCLIB_test.h> + +int main() +{ + BEGIN_TESTS; + /* tests covered in malloc test driver */ + return TEST_RESULTS; +} + +#endif diff --git a/functions/stdlib/malloc.c b/functions/stdlib/malloc.c new file mode 100644 index 0000000..c767b17 --- /dev/null +++ b/functions/stdlib/malloc.c @@ -0,0 +1,221 @@ +/* $Id$ */ + +/* Release $Name$ */ + +/* void * malloc( size_t ) + + This file is part of the Public Domain C Library (PDCLib). + Permission is granted to use, modify, and / or redistribute at will. +*/ + +#include + +#ifndef REGTEST + +#include + +#ifndef _PDCLIB_INT_H +#define _PDCLIB_INT_H _PDLIB_INT_H +#include <_PDCLIB_int.h> +#endif + +/* TODO: Primitive placeholder. Much room for improvement. */ + +/* 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 ) +{ + if ( size == 0 ) + { + return NULL; + } + if ( size < _PDCLIB_MINALLOC ) + { + 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 ) + { + /* Found exact fit, allocate node */ + if ( previous != NULL ) + { + /* Node in the middle of the list */ + previous->next = current->next; + } + else + { + /* 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; + } + /* No exact fit; go for first fit */ + if ( firstfit != NULL ) + { + if ( ( firstfit->size - size ) > _PDCLIB_MINALLOC ) + { + /* 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 ); + } + 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 ) + { + /* Node is last in list */ + _PDCLIB_memlist.last = firstfit_previous; + } + return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ); + } + } + { + /* No fit possible; how many additional pages do we need? */ + uintmax_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( pages ); + if ( newnode != NULL ) + { + newnode->next = NULL; + newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t ); + if ( ( newnode->size - size ) > _PDCLIB_MINALLOC ) + { + /* 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; + splitnode->next = NULL; + } + else + { + _PDCLIB_memlist.last->next = splitnode; + } + _PDCLIB_memlist.last = splitnode; + } + 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 + +#define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr ) +#define PAGETEST( x ) ( pages_start + x * _PDCLIB_PAGESIZE ) == sbrk( 0 ) +#define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t ) + +/* 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. +*/ + +#include + +int main( int argc, char * argv[] ) +{ + BEGIN_TESTS; +#ifndef REGTEST + { + void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8; + char * pages_start = _PDCLIB_allocpages( 0 ); + /* allocating 10 byte; expected: 1 page allocation, node split */ + TESTCASE( MEMTEST( ptr1, 10 ) ); + TESTCASE( PAGETEST( 1 ) ); + /* allocating EFFECTIVE - 10 byte; expected: no page allocation, receiving split node */ + TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) ); + TESTCASE( PAGETEST( 1 ) ); + /* allocating EFFECTIVE; expected: 1 page allocation, no node split */ + TESTCASE( MEMTEST( ptr3, EFFECTIVE ) ); + TESTCASE( PAGETEST( 2 ) ); + /* allocating EFFECTIVE - 4; expected: 1 page allocation, no node split */ + TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) ); + TESTCASE( PAGETEST( 3 ) ); + /* freeing and re-allocating EFFECTIVE - 4; expected: no page allocation, no node split */ + free( ptr4 ); + TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) ); + TESTCASE( ptr4 == ptr5 ); + TESTCASE( PAGETEST( 3 ) ); + /* releasing EFFECTIVE; expected: no page release */ + free( ptr3 ); + TESTCASE( PAGETEST( 3 ) ); + /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: 2 page allocation, no node split */ + TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) ); + TESTCASE( PAGETEST( 5 ) ); + /* reallocating to 10 byte; expected: no page allocation, no node split */ + TESTCASE( realloc( ptr3, 10 ) == ptr3 ); + TESTCASE( PAGETEST( 5 ) ); + /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */ + TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 ); + TESTCASE( PAGETEST( 5 ) ); + /* reallocating to EFFECTIVE + _PDCLIB_PAGESIZE * 2; expected: 3 page allocations, no node split */ + TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 ); + TESTCASE( PAGETEST( 8 ) ); + /* allocating EFFECTIVE + _PDCLIB_PAGESIZE; expected: no page allocation, no node split */ + TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) ); + TESTCASE( PAGETEST( 8 ) ); + /* allocating zero size; expected: no page allocation, no node split */ + TESTCASE( ! MEMTEST( ptr6, 0 ) ); + TESTCASE( PAGETEST( 8 ) ); + /* allocating 4 byte; expected: no page allocation, upsizing of size, node split */ + TESTCASE( MEMTEST( ptr7, 4 ) ); + TESTCASE( PAGETEST( 8 ) ); + /* allocating rest of page; expected: no page allocation, no node split */ + TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) ); + TESTCASE( PAGETEST( 8 ) ); + /* freeing, and allocating one byte more; expected: 1 page allocation, node split */ + free( ptr8 ); + TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) ); + TESTCASE( PAGETEST( 9 ) ); + } +#endif + return TEST_RESULTS; +} + +#endif diff --git a/functions/stdlib/realloc.c b/functions/stdlib/realloc.c new file mode 100644 index 0000000..df5fca1 --- /dev/null +++ b/functions/stdlib/realloc.c @@ -0,0 +1,48 @@ +/* $Id$ */ + +/* Release $Name$ */ + +/* void * realloc( void *, size_t ) + + This file is part of the Public Domain C Library (PDCLib). + Permission is granted to use, modify, and / or redistribute at will. +*/ + +#include +#include +#include + +#ifndef REGTEST + +/* TODO: Primitive placeholder. Improve. */ + +void * realloc( void * ptr, size_t size ) +{ + struct _PDCLIB_memnode_t * baseptr = (struct _PDCLIB_memnode_t *)( (char *)ptr - sizeof( struct _PDCLIB_memnode_t ) ); + if ( baseptr->size >= size ) + { + return ptr; + } + else + { + void * newptr = malloc( size ); + memcpy( newptr, ptr, baseptr->size ); + free( ptr ); + return newptr; + } + return NULL; +} + +#endif + +#ifdef TEST +#include <_PDCLIB_test.h> + +int main() +{ + BEGIN_TESTS; + /* tests covered in malloc test driver */ + return TEST_RESULTS; +} + +#endif diff --git a/internals/_PDCLIB_config.h b/internals/_PDCLIB_config.h index 2fa66c7..41fe02c 100644 --- a/internals/_PDCLIB_config.h +++ b/internals/_PDCLIB_config.h @@ -121,7 +121,7 @@ struct _PDCLIB_lldiv_t */ #define _PDCLIB_SIG_ATOMIC INT -/* Result type of the 'sizeof' operator */ +/* Result type of the 'sizeof' operator (must be unsigned) */ #define _PDCLIB_size unsigned int #define _PDCLIB_SIZE UINT @@ -207,4 +207,25 @@ typedef char * _PDCLIB_va_list; /* -------------------------------------------------------------------------- */ /* A system call that terminates the calling process */ +void _exit( int status ) __attribute__(( noreturn )); #define _PDCLIB_Exit( x ) _exit( x ) + +/* Memory management */ + +/* Set this to the page size of your OS. If your OS does not support paging, set + to an appropriate value. (Too small, and malloc() will call the kernel too + often. Too large, and you will waste memory. +*/ +#define _PDCLIB_PAGESIZE 4096 + +/* Set this to the minimum memory node size. Any malloc() for a smaller siz + will be satisfied by a malloc() of this size instead. +*/ +#define _PDCLIB_MINALLOC 8 + +/* Request another x pages (of size _PDCLIB_PAGESIZE) of memory from the kernel, + or release them back to the kernel if n is negative. + Return a (void *) pointing to the former end-of-heap if successful, NULL + otherwise. +*/ +void * _PDCLIB_allocpages( int n ); diff --git a/platform/example/_PDCLIB/allocpages.c b/platform/example/_PDCLIB/allocpages.c new file mode 100644 index 0000000..48b8dc9 --- /dev/null +++ b/platform/example/_PDCLIB/allocpages.c @@ -0,0 +1,86 @@ +/* $Id$ */ + +/* Release $Name$ */ + +/* _PDCLIB_allocpages( int const ) + + This file is part of the Public Domain C Library (PDCLib). + Permission is granted to use, modify, and / or redistribute at will. +*/ + +/* This is an example implementation of _PDCLIB_allocpages() (declared in + _PDCLIB_config.h), fit for use with POSIX kernels. +*/ + +#include + +#include + +#ifndef _PDCLIB_CONFIG_H +#define _PDCLIB_CONFIG_H _PDCLIB_CONFIG_H +#include <_PDCLIB_config.h> +#endif + +static void * membreak = NULL; + +void * _PDCLIB_allocpages( int const n ) +{ + if ( membreak == NULL ) + { + /* first call, make sure end-of-heap is page-aligned */ + intptr_t unaligned = 0; + membreak = sbrk( 0 ); + unaligned = _PDCLIB_PAGESIZE - (intptr_t)membreak % _PDCLIB_PAGESIZE; + if ( unaligned < _PDCLIB_PAGESIZE ) + { + /* end-of-heap not page-aligned - adjust */ + if ( sbrk( unaligned ) != membreak ) + { + /* error */ + return NULL; + } + membreak += unaligned; + } + } + /* increasing or decreasing heap - standard operation */ + void * oldbreak = membreak; + membreak = (void *)( (char *)membreak + ( n * _PDCLIB_PAGESIZE ) ); + if ( brk( membreak ) == 0 ) + { + /* successful */ + return oldbreak; + } + else + { + /* out of memory */ + membreak = oldbreak; + return NULL; + } +} + +#ifdef TEST +#include <_PDCLIB_test.h> + +int puts( const char * ); + +int main() +{ + BEGIN_TESTS; +#ifndef REGTEST + { + void * startbreak = sbrk( 0 ); + TESTCASE( _PDCLIB_allocpages( 0 ) ); + TESTCASE( ( sbrk( 0 ) - startbreak ) <= _PDCLIB_PAGESIZE ); + startbreak = sbrk( 0 ); + TESTCASE( _PDCLIB_allocpages( 1 ) ); + TESTCASE( sbrk( 0 ) == startbreak + ( 1 * _PDCLIB_PAGESIZE ) ); + TESTCASE( _PDCLIB_allocpages( 5 ) ); + TESTCASE( sbrk( 0 ) == startbreak + ( 6 * _PDCLIB_PAGESIZE ) ); + TESTCASE( _PDCLIB_allocpages( -3 ) ); + TESTCASE( sbrk( 0 ) == startbreak + ( 3 * _PDCLIB_PAGESIZE ) ); + } +#endif + return TEST_RESULTS; +} + +#endif