3 /* void * malloc( size_t )
5 This file is part of the Public Domain C Library (PDCLib).
6 Permission is granted to use, modify, and / or redistribute at will.
15 #ifndef _PDCLIB_GLUE_H
16 #define _PDCLIB_GLUE_H _PDLIB_GLUE_H
17 #include <_PDCLIB_glue.h>
20 /* TODO: Primitive placeholder. Much room for improvement. */
22 /* Keeping pointers to the first and the last element of the free list. */
23 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
25 void * malloc( size_t size )
31 if ( size < _PDCLIB_MINALLOC )
33 size = _PDCLIB_MINALLOC;
36 struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
37 struct _PDCLIB_memnode_t * previous = NULL;
38 struct _PDCLIB_memnode_t * firstfit = NULL;
39 struct _PDCLIB_memnode_t * firstfit_previous = NULL;
40 /* Trying exact fit */
41 while ( current != NULL )
43 if ( current->size == size )
45 /* Found exact fit, allocate node */
46 if ( previous != NULL )
48 /* Node in the middle of the list */
49 previous->next = current->next;
53 /* Node is first in list */
54 _PDCLIB_memlist.first = current->next;
56 if ( _PDCLIB_memlist.last == current )
58 /* Node is last in list */
59 _PDCLIB_memlist.last = previous;
61 return (char *)current + sizeof( struct _PDCLIB_memnode_t );
63 else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
65 /* Remember previous node in case we do not get an exact fit.
66 Note that this is the node *pointing to* the first fit,
67 as we need that for allocating (i.e., changing next pointer).
69 firstfit_previous = previous;
72 /* Skip to next node */
74 current = current->next;
76 /* No exact fit; go for first fit */
77 if ( firstfit != NULL )
79 bool node_split = false;
80 if ( ( firstfit->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
82 /* Oversized - split into two nodes */
83 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
84 newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
85 newnode->next = firstfit->next;
86 firstfit->next = newnode;
87 firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
90 if ( firstfit_previous != NULL )
92 /* Node in the middle of the list */
93 firstfit_previous->next = firstfit->next;
97 /* Node is first in list */
98 _PDCLIB_memlist.first = firstfit->next;
100 if ( _PDCLIB_memlist.last == firstfit )
102 /* Node is last in list */
105 _PDCLIB_memlist.last = firstfit->next;
109 _PDCLIB_memlist.last = firstfit_previous;
112 return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
116 /* No fit possible; how many additional pages do we need? */
117 size_t pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
118 /* Allocate more pages */
119 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( (int)pages );
120 if ( newnode != NULL )
122 newnode->next = NULL;
123 newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
124 if ( ( newnode->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
126 /* Oversized - split into two nodes */
127 struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
128 splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
129 newnode->size = size;
130 /* Add splitted node as last element to free node list */
131 if ( _PDCLIB_memlist.last == NULL )
133 _PDCLIB_memlist.first = splitnode;
137 _PDCLIB_memlist.last->next = splitnode;
139 splitnode->next = NULL; /* TODO: This is bug #7, uncovered by testdriver yet. */
140 _PDCLIB_memlist.last = splitnode;
142 return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
145 /* No fit, heap extension not possible - out of memory */
153 #include <_PDCLIB_test.h>
161 /* Effective page size, i.e. how many bytes can be allocated and still be on
164 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
165 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
167 char * pages_start = 0;
168 int test_nodes( char const * const, int, ... );
169 void PRINT( char const * const, ... );
171 /* This can be enabled to give a dump of node information */
173 void PRINT( char const * const format, ... )
176 va_start( ap, format );
177 vprintf( format, ap );
180 void PRINT( char const * const format, ... )
186 /* Helper function checking number of allocated memory pages and the nodes
187 in the free memory list against expectations.
189 int test_nodes( char const * const action, int expected_pages, ... )
191 static int count = 1;
194 /* Determining the amount of allocated pages */
195 int allocated_pages = ( (intptr_t)_PDCLIB_allocpages( 0 ) - (intptr_t)pages_start ) / _PDCLIB_PAGESIZE;
196 PRINT( "Test #%2d, %d allocated pages", count++, allocated_pages );
197 if ( allocated_pages != expected_pages )
199 PRINT( " - MISMATCH, expected\n %d pages\n", expected_pages );
206 /* Now moving through the free nodes list */
208 va_start( ap, expected_pages );
209 struct _PDCLIB_memnode_t * tracer = _PDCLIB_memlist.first;
212 while ( tracer != NULL )
215 size_t node_location = (char *)tracer - (char *)pages_start;
216 PRINT( " - node %.4p, size %#.4x", node_location, tracer->size );
218 size_t expected_location = va_arg( ap, size_t );
219 if ( expected_location == 0 )
221 PRINT( " - UNEXPECTED NODE\n" );
225 /* Memorizing first and last expected node for later comparison. */
226 if ( firstnode == 0 )
228 firstnode = expected_location;
230 lastnode = expected_location;
231 /* Comparing expected node against current node */
232 size_t expected_size = va_arg( ap, size_t );
233 if ( ( node_location != expected_location ) || ( tracer->size != expected_size ) )
235 PRINT( " - MISMATCH, expected values\n %.4p %#.4p\n", expected_location, expected_size );
242 tracer = tracer->next;
244 /* Comparing first and last node in memlist against expectations. */
245 PRINT( " - memlist first: %#.4x - last: %#.4x",
246 ( _PDCLIB_memlist.first == NULL ) ? NULL : (char *)_PDCLIB_memlist.first - (char *)pages_start,
247 ( _PDCLIB_memlist.last == NULL ) ? NULL : (char *)_PDCLIB_memlist.last - (char *)pages_start );
248 if ( ( firstnode != 0 ) &&
249 ( ( ( (char *)_PDCLIB_memlist.first - (char *)pages_start ) != firstnode )
250 || ( ( (char *)_PDCLIB_memlist.last - (char *)pages_start ) != lastnode ) ) )
252 PRINT( " - MISMATCH, expected values\n %#.4x - last: %#.4x\n", firstnode, lastnode );
265 /* Note that this test driver heavily tests *internals* of the implementation
266 above (and of free() and realloc(), too). That means that changes in the
267 implementation must be accompanied with appropriate changes of the test
268 driver. It does *not* make a good regression tester for the implementation,
269 I am afraid, and thus there is no REGTEST equivalent.
275 void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9, * ptrA, * ptrB, * ptrC;
277 pages_start = _PDCLIB_allocpages( 0 );
278 PRINT( "\nEffective is: %#.4x\nsizeof( memnode ) is: %#.2x\n\n", EFFECTIVE, sizeof( struct _PDCLIB_memnode_t ) );
280 /* Allocating 10 bytes; expecting one page allocation and a node split */
281 TESTCASE( MEMTEST( ptr1, 10 ) );
282 TESTCASE( test_nodes( "Allocating 10 bytes.", 1,
283 sizeof( struct _PDCLIB_memnode_t ) + 10, EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - 10,
286 /* Allocating the rest of the page; expecting no page allocation and assignment of the remaining node */
287 TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
288 TESTCASE( test_nodes( "Allocating the rest of the page.", 1,
291 /* Allocating a full page; expecting one page allocation, no node split */
292 TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
293 TESTCASE( test_nodes( "Allocating a full page.", 2,
296 /* Allocating *almost* a full page; expecting one page allocation, no node split */
297 TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
298 TESTCASE( test_nodes( "Allocating *almost* a full page.", 3,
301 /* Freeing and re-allocating the "almost" full page; expecting no page allocation, no node split */
303 TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
304 TESTCASE( ptr4 == ptr5 );
305 TESTCASE( test_nodes( "Freeing and re-allocating the \"almost\" full page.", 3 ) );
307 /* Freeing the full page from test #3; expecting a full-sized free node. */
309 TESTCASE( test_nodes( "Freeing the full page from test #3.", 3,
310 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
313 /* Allocating two full pages; expecting two page allocations, no node split */
314 TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
315 TESTCASE( test_nodes( "Allocating two full pages.", 5,
316 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
319 /* Re-allocating to size of 10 bytes; expecting no page allocation, no node split */
320 /* TODO: Shouldn't realloc() split the now much-too-large node? */
321 TESTCASE( realloc( ptr3, 10 ) == ptr3 );
322 TESTCASE( test_nodes( "Re-allocating to size of 10 bytes.", 5,
323 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
326 /* Re-allocating to size of two full pages; expecting no page allocation, no node split */
327 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
328 TESTCASE( test_nodes( "Re-allocating to size of two full pages.", 5,
329 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
332 /* Re-allocating to size of three full pages; expecting three page allocation, freeing of two-page node */
333 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
334 TESTCASE( test_nodes( "Re-allocating to size of three full pages.", 8,
335 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
336 _PDCLIB_PAGESIZE * 3, EFFECTIVE + _PDCLIB_PAGESIZE,
339 /* Allocating two full pages; expecting allocation of the available two-page node */
340 TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
341 TESTCASE( test_nodes( "Allocating two full pages.", 8,
342 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
345 /* Allocating zero bytes; expecting no change */
346 TESTCASE( ! MEMTEST( ptr6, 0 ) );
347 TESTCASE( test_nodes( "Allocating zero bytes.", 8,
348 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
351 /* Allocating 4 bytes; expecting upsizing of requestupsizing of size, node split */
352 TESTCASE( MEMTEST( ptr7, 4 ) );
353 TESTCASE( test_nodes( "Allocating 4 bytes.", 8,
354 _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
355 EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
358 /* Allocating the rest of the page; expecting no page allocation and assignment of the remaining node */
359 TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
360 TESTCASE( test_nodes( "Allocating the rest of the page.", 8, 0 ) );
362 /* Freeing the node from the previous test; expecting node to re-appear in free list */
364 TESTCASE( test_nodes( "Freeing the node from the previous test.", 8,
365 _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
366 EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
369 /* Allocating one byte more than available in free node; expecting page allocation */
370 TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
371 TESTCASE( test_nodes( "Allocating one byte more than available in free node.", 9,
372 _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
373 EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
376 /* Re-allocating with NULL pointer; expecting no page allocation, no node split */
377 ptr9 = realloc( NULL, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) );
378 TESTCASE( ptr9 != NULL );
379 TESTCASE( memset( ptr9, 0, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) == ptr9 );
380 TESTCASE( test_nodes( "Re-allocating with NULL pointer.", 9, 0 ) );
382 /* Allocating a bit more than half a page; expecting page allocation, node split */
383 #define TESTSIZE 3000
384 TESTCASE( MEMTEST( ptrA, TESTSIZE ) );
385 TESTCASE( test_nodes( "Allocating a bit more than half a page.", 10,
386 _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
387 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
390 /* Allocating a bit more than half a page; expecting page allocation, node split */
391 TESTCASE( MEMTEST( ptrB, TESTSIZE ) );
392 TESTCASE( test_nodes( "Allocating a bit more than half a page.", 11,
393 _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
394 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
395 _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
396 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
399 /* Allocating a bit more than half a page; expecting page allocation, node split */
400 TESTCASE( MEMTEST( ptrC, TESTSIZE ) );
401 TESTCASE( test_nodes( "Allocating a bit more than half a page.", 12,
402 _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
403 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
404 _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
405 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
406 _PDCLIB_PAGESIZE * 11 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
407 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
410 /* Freeing the middle node */
412 TESTCASE( test_nodes( "Freeing the middle node.", 12,
413 _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
414 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
415 _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
416 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
417 _PDCLIB_PAGESIZE * 11 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
418 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
419 _PDCLIB_PAGESIZE * 10,
424 puts( " NOTEST malloc() test driver is PDCLib-specific." );