[avr-libc-dev] malloc improvement

[Gerben van den Broeke]

Current implementation:
malloc loops trough all the holes in the freelist, checking if there is a hole 
with exactly the right size (len), in which case it takes the hole and returns 
it.
While looping it also notes down the size of the smallest hole it has found 
that is still big enough (size > len).
If it cannot find a hole with exactly the right size, it will use this noted 
hole.
But because it only noted the size of the hole, it loops through all the holes 
again until it has found a hole with that size, then uses that hole.

Improvement:
By not only noting down the size of the smallest hole, but also noting its 
addrress, the second loop is not necessary anymore.

The cost:
2 more pointers are needed (both the found hole and the hole before it must be 
remembered), so it might add 4 pushes at the beginning and 4 pops at the end of 
the function.
In the first loop two movw's are needed to note down the hole address, which 
are executed everytime a smaller hole is found.

The gain:
The whole second loop can be removed, which saves much program space (whole 
malloc becomes about 10% smaller) and even more execution time.


By the way, I also found a little problem with malloc that occurs when 
__malloc_heap_end has not been defined (quite normal), so cp = STACK_POINTER() 
- __malloc_margin is used as heap end, and the available space is calculated as 
avail = cp - __brkval;
If the stack pointer would have become lower than __brkval + __malloc_margin, 
then avail (being a size_t) would become less than zero = very much, so malloc 
would allocate the space which belongs to the stack.
This can happen easily when the heap is filled (almost) up to the stackpointer 
- __malloc_margin, then just one or maybe a few pushes are done so there is 
less than __malloc_margin between heap end and stackpointer, and then malloc is 
called.
I suggest the cp and __brkval should first be compared: if (cp < __brkval) 
return 0; or avail could be a signed integer (which is no problem as long as 
there is less than 32KB of memory); note that this fix is *not* included in the 
attached patch.

Gerben

diff
Description: Text Data

signature.asc
Description: This is a digitally signed message part.