1 /* void * malloc( size_t )
3 This file is part of the Public Domain C Library (PDCLib).
4 Permission is granted to use, modify, and / or redistribute at will.
12 #include <_PDCLIB_glue.h>
14 /* TODO: Primitive placeholder. Much room for improvement. */
16 /* Keeping pointers to the first and the last element of the free list. */
17 struct _PDCLIB_headnode_t _PDCLIB_memlist = { NULL, NULL };
19 void * malloc( size_t size )
25 if ( size < _PDCLIB_MINALLOC )
27 size = _PDCLIB_MINALLOC;
30 struct _PDCLIB_memnode_t * current = _PDCLIB_memlist.first;
31 struct _PDCLIB_memnode_t * previous = NULL;
32 struct _PDCLIB_memnode_t * firstfit = NULL;
33 struct _PDCLIB_memnode_t * firstfit_previous = NULL;
34 /* Trying exact fit */
35 while ( current != NULL )
37 if ( current->size == size )
39 /* Found exact fit, allocate node */
40 if ( previous != NULL )
42 /* Node in the middle of the list */
43 previous->next = current->next;
47 /* Node is first in list */
48 _PDCLIB_memlist.first = current->next;
50 if ( _PDCLIB_memlist.last == current )
52 /* Node is last in list */
53 _PDCLIB_memlist.last = previous;
55 return (char *)current + sizeof( struct _PDCLIB_memnode_t );
57 else if ( current->size > size && ( firstfit == NULL || current->size < firstfit->size ) )
59 /* Remember previous node in case we do not get an exact fit.
60 Note that this is the node *pointing to* the first fit,
61 as we need that for allocating (i.e., changing next pointer).
63 firstfit_previous = previous;
66 /* Skip to next node */
68 current = current->next;
70 /* No exact fit; go for first fit */
71 if ( firstfit != NULL )
73 bool node_split = false;
74 if ( ( firstfit->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
76 /* Oversized - split into two nodes */
77 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)( (char *)firstfit + sizeof( struct _PDCLIB_memnode_t ) + size );
78 newnode->size = firstfit->size - size - sizeof( struct _PDCLIB_memnode_t );
79 newnode->next = firstfit->next;
80 firstfit->next = newnode;
81 firstfit->size = firstfit->size - newnode->size - sizeof( struct _PDCLIB_memnode_t );
84 if ( firstfit_previous != NULL )
86 /* Node in the middle of the list */
87 firstfit_previous->next = firstfit->next;
91 /* Node is first in list */
92 _PDCLIB_memlist.first = firstfit->next;
94 if ( _PDCLIB_memlist.last == firstfit )
96 /* Node is last in list */
99 _PDCLIB_memlist.last = firstfit->next;
103 _PDCLIB_memlist.last = firstfit_previous;
106 return (char *)firstfit + sizeof( struct _PDCLIB_memnode_t );
110 /* No fit possible; how many additional pages do we need? */
111 size_t pages = ( ( size + sizeof( struct _PDCLIB_memnode_t ) - 1 ) / _PDCLIB_PAGESIZE ) + 1;
112 /* Allocate more pages */
113 struct _PDCLIB_memnode_t * newnode = (struct _PDCLIB_memnode_t *)_PDCLIB_allocpages( (int)pages );
114 if ( newnode != NULL )
116 newnode->next = NULL;
117 newnode->size = pages * _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t );
118 if ( ( newnode->size - size ) > ( _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ) ) )
120 /* Oversized - split into two nodes */
121 struct _PDCLIB_memnode_t * splitnode = (struct _PDCLIB_memnode_t *)( (char *)newnode + sizeof( struct _PDCLIB_memnode_t ) + size );
122 splitnode->size = newnode->size - size - sizeof( struct _PDCLIB_memnode_t );
123 newnode->size = size;
124 /* Add splitted node as last element to free node list */
125 if ( _PDCLIB_memlist.last == NULL )
127 _PDCLIB_memlist.first = splitnode;
131 _PDCLIB_memlist.last->next = splitnode;
133 splitnode->next = NULL; /* TODO: This is bug #7, uncovered by testdriver yet. */
134 _PDCLIB_memlist.last = splitnode;
136 return (char *)newnode + sizeof( struct _PDCLIB_memnode_t );
139 /* No fit, heap extension not possible - out of memory */
147 #include <_PDCLIB_test.h>
155 /* Effective page size, i.e. how many bytes can be allocated and still be on
158 #define EFFECTIVE _PDCLIB_PAGESIZE - sizeof( struct _PDCLIB_memnode_t )
159 #define MEMTEST( ptr, size ) ( ( ptr = malloc( size ) ) != NULL ) && ( memset( ptr, 0, size ) == ptr )
161 char * pages_start = 0;
162 int test_nodes( char const * const, int, ... );
163 void PRINT( char const * const, ... );
165 /* This can be enabled to give a dump of node information */
167 void PRINT( char const * const format, ... )
170 va_start( ap, format );
171 vprintf( format, ap );
174 void PRINT( char const * const format, ... )
180 /* Helper function checking number of allocated memory pages and the nodes
181 in the free memory list against expectations.
183 int test_nodes( char const * const action, int expected_pages, ... )
185 static int count = 1;
188 /* Determining the amount of allocated pages */
189 int allocated_pages = ( (intptr_t)_PDCLIB_allocpages( 0 ) - (intptr_t)pages_start ) / _PDCLIB_PAGESIZE;
190 PRINT( "Test #%2d, %d allocated pages", count++, allocated_pages );
191 if ( allocated_pages != expected_pages )
193 PRINT( " - MISMATCH, expected\n %d pages\n", expected_pages );
200 /* Now moving through the free nodes list */
202 va_start( ap, expected_pages );
203 struct _PDCLIB_memnode_t * tracer = _PDCLIB_memlist.first;
206 while ( tracer != NULL )
209 size_t node_location = (char *)tracer - (char *)pages_start;
210 PRINT( " - node %.4p, size %#.4x", node_location, tracer->size );
212 size_t expected_location = va_arg( ap, size_t );
213 if ( expected_location == 0 )
215 PRINT( " - UNEXPECTED NODE\n" );
219 /* Memorizing first and last expected node for later comparison. */
220 if ( firstnode == 0 )
222 firstnode = expected_location;
224 lastnode = expected_location;
225 /* Comparing expected node against current node */
226 size_t expected_size = va_arg( ap, size_t );
227 if ( ( node_location != expected_location ) || ( tracer->size != expected_size ) )
229 PRINT( " - MISMATCH, expected values\n %.4p %#.4p\n", expected_location, expected_size );
236 tracer = tracer->next;
238 /* Comparing first and last node in memlist against expectations. */
239 PRINT( " - memlist first: %#.4x - last: %#.4x",
240 ( _PDCLIB_memlist.first == NULL ) ? NULL : (char *)_PDCLIB_memlist.first - (char *)pages_start,
241 ( _PDCLIB_memlist.last == NULL ) ? NULL : (char *)_PDCLIB_memlist.last - (char *)pages_start );
242 if ( ( firstnode != 0 ) &&
243 ( ( ( (char *)_PDCLIB_memlist.first - (char *)pages_start ) != firstnode )
244 || ( ( (char *)_PDCLIB_memlist.last - (char *)pages_start ) != lastnode ) ) )
246 PRINT( " - MISMATCH, expected values\n %#.4x - last: %#.4x\n", firstnode, lastnode );
259 /* Note that this test driver heavily tests *internals* of the implementation
260 above (and of free() and realloc(), too). That means that changes in the
261 implementation must be accompanied with appropriate changes of the test
262 driver. It does *not* make a good regression tester for the implementation,
263 I am afraid, and thus there is no REGTEST equivalent.
269 void * ptr1, * ptr2, * ptr3, * ptr4, * ptr5, * ptr6, * ptr7, * ptr8, * ptr9, * ptrA, * ptrB, * ptrC;
271 pages_start = _PDCLIB_allocpages( 0 );
272 PRINT( "\nEffective is: %#.4x\nsizeof( memnode ) is: %#.2x\n\n", EFFECTIVE, sizeof( struct _PDCLIB_memnode_t ) );
274 /* Allocating 10 bytes; expecting one page allocation and a node split */
275 TESTCASE( MEMTEST( ptr1, 10 ) );
276 TESTCASE( test_nodes( "Allocating 10 bytes.", 1,
277 sizeof( struct _PDCLIB_memnode_t ) + 10, EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - 10,
280 /* Allocating the rest of the page; expecting no page allocation and assignment of the remaining node */
281 TESTCASE( MEMTEST( ptr2, EFFECTIVE - 10 - sizeof( struct _PDCLIB_memnode_t ) ) );
282 TESTCASE( test_nodes( "Allocating the rest of the page.", 1,
285 /* Allocating a full page; expecting one page allocation, no node split */
286 TESTCASE( MEMTEST( ptr3, EFFECTIVE ) );
287 TESTCASE( test_nodes( "Allocating a full page.", 2,
290 /* Allocating *almost* a full page; expecting one page allocation, no node split */
291 TESTCASE( MEMTEST( ptr4, EFFECTIVE - 4 ) );
292 TESTCASE( test_nodes( "Allocating *almost* a full page.", 3,
295 /* Freeing and re-allocating the "almost" full page; expecting no page allocation, no node split */
297 TESTCASE( MEMTEST( ptr5, EFFECTIVE - 4 ) );
298 TESTCASE( ptr4 == ptr5 );
299 TESTCASE( test_nodes( "Freeing and re-allocating the \"almost\" full page.", 3 ) );
301 /* Freeing the full page from test #3; expecting a full-sized free node. */
303 TESTCASE( test_nodes( "Freeing the full page from test #3.", 3,
304 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
307 /* Allocating two full pages; expecting two page allocations, no node split */
308 TESTCASE( MEMTEST( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) );
309 TESTCASE( test_nodes( "Allocating two full pages.", 5,
310 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
313 /* Re-allocating to size of 10 bytes; expecting no page allocation, no node split */
314 /* TODO: Shouldn't realloc() split the now much-too-large node? */
315 TESTCASE( realloc( ptr3, 10 ) == ptr3 );
316 TESTCASE( test_nodes( "Re-allocating to size of 10 bytes.", 5,
317 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
320 /* Re-allocating to size of two full pages; expecting no page allocation, no node split */
321 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE ) == ptr3 );
322 TESTCASE( test_nodes( "Re-allocating to size of two full pages.", 5,
323 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
326 /* Re-allocating to size of three full pages; expecting three page allocation, freeing of two-page node */
327 TESTCASE( realloc( ptr3, EFFECTIVE + _PDCLIB_PAGESIZE * 2 ) != ptr3 );
328 TESTCASE( test_nodes( "Re-allocating to size of three full pages.", 8,
329 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
330 _PDCLIB_PAGESIZE * 3, EFFECTIVE + _PDCLIB_PAGESIZE,
333 /* Allocating two full pages; expecting allocation of the available two-page node */
334 TESTCASE( MEMTEST( ptr4, EFFECTIVE + _PDCLIB_PAGESIZE ) );
335 TESTCASE( test_nodes( "Allocating two full pages.", 8,
336 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
339 /* Allocating zero bytes; expecting no change */
340 TESTCASE( ! MEMTEST( ptr6, 0 ) );
341 TESTCASE( test_nodes( "Allocating zero bytes.", 8,
342 _PDCLIB_PAGESIZE * 1, EFFECTIVE,
345 /* Allocating 4 bytes; expecting upsizing of requestupsizing of size, node split */
346 TESTCASE( MEMTEST( ptr7, 4 ) );
347 TESTCASE( test_nodes( "Allocating 4 bytes.", 8,
348 _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
349 EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
352 /* Allocating the rest of the page; expecting no page allocation and assignment of the remaining node */
353 TESTCASE( MEMTEST( ptr8, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
354 TESTCASE( test_nodes( "Allocating the rest of the page.", 8, 0 ) );
356 /* Freeing the node from the previous test; expecting node to re-appear in free list */
358 TESTCASE( test_nodes( "Freeing the node from the previous test.", 8,
359 _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
360 EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
363 /* Allocating one byte more than available in free node; expecting page allocation */
364 TESTCASE( MEMTEST( ptr8, EFFECTIVE + 1 - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) );
365 TESTCASE( test_nodes( "Allocating one byte more than available in free node.", 9,
366 _PDCLIB_PAGESIZE * 1 + _PDCLIB_MINALLOC + sizeof( struct _PDCLIB_memnode_t ),
367 EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ),
370 /* Re-allocating with NULL pointer; expecting no page allocation, no node split */
371 ptr9 = realloc( NULL, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) );
372 TESTCASE( ptr9 != NULL );
373 TESTCASE( memset( ptr9, 0, EFFECTIVE - _PDCLIB_MINALLOC - sizeof( struct _PDCLIB_memnode_t ) ) == ptr9 );
374 TESTCASE( test_nodes( "Re-allocating with NULL pointer.", 9, 0 ) );
376 /* Allocating a bit more than half a page; expecting page allocation, node split */
377 #define TESTSIZE 3000
378 TESTCASE( MEMTEST( ptrA, TESTSIZE ) );
379 TESTCASE( test_nodes( "Allocating a bit more than half a page.", 10,
380 _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
381 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
384 /* Allocating a bit more than half a page; expecting page allocation, node split */
385 TESTCASE( MEMTEST( ptrB, TESTSIZE ) );
386 TESTCASE( test_nodes( "Allocating a bit more than half a page.", 11,
387 _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
388 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
389 _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
390 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
393 /* Allocating a bit more than half a page; expecting page allocation, node split */
394 TESTCASE( MEMTEST( ptrC, TESTSIZE ) );
395 TESTCASE( test_nodes( "Allocating a bit more than half a page.", 12,
396 _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
397 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
398 _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
399 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
400 _PDCLIB_PAGESIZE * 11 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
401 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
404 /* Freeing the middle node */
406 TESTCASE( test_nodes( "Freeing the middle node.", 12,
407 _PDCLIB_PAGESIZE * 9 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
408 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
409 _PDCLIB_PAGESIZE * 10 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
410 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
411 _PDCLIB_PAGESIZE * 11 + sizeof( struct _PDCLIB_memnode_t ) + TESTSIZE,
412 EFFECTIVE - sizeof( struct _PDCLIB_memnode_t ) - TESTSIZE,
413 _PDCLIB_PAGESIZE * 10,
418 puts( " NOTEST malloc() test driver is PDCLib-specific." );