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.
14 #include <_PDCLIB_glue.h>
16 /* TODO: Primitive placeholder. Much room for improvement. */
18 /* Keeping pointers to the first and the last element of the free list. */
19 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
21 void * malloc( size_t size )
27 if ( size < _PDCLIB_MINALLOC )
29 size = _PDCLIB_MINALLOC;
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 )
39 if ( current->size == size )
41 /* Found exact fit, allocate node */
42 if ( previous != NULL )
44 /* Node in the middle of the list */
45 previous->next = current->next;
49 /* Node is first in list */
50 _PDCLIB_memlist.first = current->next;
52 if ( _PDCLIB_memlist.last == current )
54 /* Node is last in list */
55 _PDCLIB_memlist.last = previous;
57 return (char *)current + sizeof( struct _PDCLIB_memnode_t );
59 else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
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).
65 firstfit_previous = previous;
68 /* Skip to next node */
70 current = current->next;
72 /* No exact fit; go for first fit */
73 if ( firstfit != NULL )
75 bool node_split = false;
76 if ( ( firstfit->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
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 );
86 if ( firstfit_previous != NULL )
88 /* Node in the middle of the list */
89 firstfit_previous->next = firstfit->next;
93 /* Node is first in list */
94 _PDCLIB_memlist.first = firstfit->next;
96 if ( _PDCLIB_memlist.last == firstfit )
98 /* Node is last in list */
101 _PDCLIB_memlist.last = firstfit->next;
105 _PDCLIB_memlist.last = firstfit_previous;
108 return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
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 )
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 ) ) )
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 )
129 _PDCLIB_memlist.first = splitnode;
133 _PDCLIB_memlist.last->next = splitnode;
135 splitnode->next = NULL; /* TODO: This is bug #7, uncovered by testdriver yet. */
136 _PDCLIB_memlist.last = splitnode;
138 return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
141 /* No fit, heap extension not possible - out of memory */
149 #include <_PDCLIB_test.h>
157 /* Effective page size, i.e. how many bytes can be allocated and still be on
160 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
161 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
163 char * pages_start = 0;
164 int test_nodes( char const * const, int, ... );
165 void PRINT( char const * const, ... );
167 /* This can be enabled to give a dump of node information */
169 void PRINT( char const * const format, ... )
172 va_start( ap, format );
173 vprintf( format, ap );
176 void PRINT( char const * const format, ... )
182 /* Helper function checking number of allocated memory pages and the nodes
183 in the free memory list against expectations.
185 int test_nodes( char const * const action, int expected_pages, ... )
187 static int count = 1;
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 )
195 PRINT( " - MISMATCH, expected\n %d pages\n", expected_pages );
202 /* Now moving through the free nodes list */
204 va_start( ap, expected_pages );
205 struct _PDCLIB_memnode_t * tracer = _PDCLIB_memlist.first;
208 while ( tracer != NULL )
211 size_t node_location = (char *)tracer - (char *)pages_start;
212 PRINT( " - node %.4p, size %#.4x", node_location, tracer->size );
214 size_t expected_location = va_arg( ap, size_t );
215 if ( expected_location == 0 )
217 PRINT( " - UNEXPECTED NODE\n" );
221 /* Memorizing first and last expected node for later comparison. */
222 if ( firstnode == 0 )
224 firstnode = expected_location;
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 ) )
231 PRINT( " - MISMATCH, expected values\n %.4p %#.4p\n", expected_location, expected_size );
238 tracer = tracer->next;
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 ) ) )
248 PRINT( " - MISMATCH, expected values\n %#.4x - last: %#.4x\n", firstnode, lastnode );
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.
271 void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9, * ptrA, * ptrB, * ptrC;
273 pages_start = _PDCLIB_allocpages( 0 );
274 PRINT( "\nEffective is: %#.4x\nsizeof( memnode ) is: %#.2x\n\n", EFFECTIVE, sizeof( struct _PDCLIB_memnode_t ) );
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,
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,
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,
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,
297 /* Freeing and re-allocating the "almost" full page; expecting no page allocation, no node split */
299 TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
300 TESTCASE( ptr4 == ptr5 );
301 TESTCASE( test_nodes( "Freeing and re-allocating the \"almost\" full page.", 3 ) );
303 /* Freeing the full page from test #3; expecting a full-sized free node. */
305 TESTCASE( test_nodes( "Freeing the full page from test #3.", 3,
306 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
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,
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,
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,
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,
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,
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,
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 ),
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 ) );
358 /* Freeing the node from the previous test; expecting node to re-appear in free list */
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 ),
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 ),
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 ) );
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,
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,
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,
406 /* Freeing the middle node */
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,
420 puts( " NOTEST malloc() test driver is PDCLib-specific." );