[U-Boot] [PATCH] malloc: improve memalign fragmentation fix

[Stephen Warren]

On 04/25/2016 03:55 PM, Stephen Warren wrote:
> From: Stephen Warren <swarren at nvidia.com>
>
> Commit 4f144a416469 "malloc: work around some memalign fragmentation
> issues" enhanced memalign() so that it can succeed in more cases where
> heap fragmentation is present. However, it did not solve as many cases
> as it could. This patch enhances the code to cover more cases.
>
> The alignment code works by allocating more space than the user requests,
> then adjusting the returned pointer to achieve alignment. In general, one
> must allocate "alignment" bytes more than the user requested in order to
> guarantee that alignment is possible. This is what the original code does.
> The previous enhancement attempted a second allocation if the padded
> allocation failed, and succeeded if that allocation just happened to be
> aligned; a fluke that happened often in practice. There are still cases
> where this could fail, yet where it is still possible to honor the user's
> allocation request. In particular, if the heap contains a free region that
> is large enough for the user's request, and for leading padding to ensure
> alignment, but has no or little space for any trailing padding. In this
> case, we can make a third(!) allocation attempt after calculating exactly
> the size of the leading padding required to achieve alignment, which is
> the minimal over-allocation needed for the overall memalign() operation to
> succeed if the third and second allocations end up at the same location.
>
> This patch isn't checkpatch-clean, since it conforms to the existing
> coding style in dlmalloc.c, which is different to the rest of U-Boot.

Tom, what do you think of this approach? Is it something we can go with? 
If so, it'd be great to apply is ASAP to clean up all the test results 
in my automated system.

An alternative might be to enhance mALLOc() to know how to search for 
aligned chunks, thus avoiding any retries. I avoided that to prevent the 
code diverging too much from the original dlmalloc.c that was imported 
from elsewhere, and keep the patch minimal. Still, that might be the 
right long-term answer.