[U-Boot] [PATCH] malloc: improve memalign fragmentation fix
From: Stephen Warren swarren@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.
Signed-off-by: Stephen Warren swarren@nvidia.com --- common/dlmalloc.c | 23 +++++++++++++++++++++-- 1 file changed, 21 insertions(+), 2 deletions(-)
diff --git a/common/dlmalloc.c b/common/dlmalloc.c index d66e80c647ce..7514d252f6eb 100644 --- a/common/dlmalloc.c +++ b/common/dlmalloc.c @@ -2838,6 +2838,7 @@ Void_t* mEMALIGn(alignment, bytes) size_t alignment; size_t bytes; * fulfill the user's request. */ if (m == NULL) { + size_t extra, extra2; /* * Use bytes not nb, since mALLOc internally calls request2size too, and * each call increases the size to allocate, to account for the header. @@ -2846,9 +2847,27 @@ Void_t* mEMALIGn(alignment, bytes) size_t alignment; size_t bytes; /* Aligned -> return it */ if ((((unsigned long)(m)) % alignment) == 0) return m; - /* Otherwise, fail */ + /* + * Otherwise, try again, requesting enough extra space to be able to + * acquire alignment. + */ fREe(m); - m = NULL; + /* Add in extra bytes to match misalignment of unexpanded allocation */ + extra = alignment - (((unsigned long)(m)) % alignment); + m = (char*)(mALLOc(bytes + extra)); + /* + * m might not be the same as before. Validate that the previous value of + * extra still works for the current value of m. + * If (!m), extra2=alignment so + */ + if (m) { + extra2 = alignment - (((unsigned long)(m)) % alignment); + if (extra2 > extra) { + fREe(m); + m = NULL; + } + } + /* Fall through to original NULL check and chunk splitting logic */ }
if (m == NULL) return NULL; /* propagate failure */
On 04/25/2016 03:55 PM, Stephen Warren wrote:
From: Stephen Warren swarren@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.
On Mon, Apr 25, 2016 at 03:55:42PM -0600, Stephen Warren wrote:
From: Stephen Warren swarren@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.
Signed-off-by: Stephen Warren swarren@nvidia.com
Reviewed-by: Tom Rini trini@konsulko.com
... for the next release, thanks!
On Mon, Apr 25, 2016 at 03:55:42PM -0600, Stephen Warren wrote:
From: Stephen Warren swarren@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.
Signed-off-by: Stephen Warren swarren@nvidia.com Reviewed-by: Tom Rini trini@konsulko.com
Applied to u-boot/master, thanks!
participants (2)
-
Stephen Warren -
Tom Rini