From mboxrd@z Thu Jan 1 00:00:00 1970 From: Stephen Warren Date: Tue, 26 Jan 2016 09:27:02 -0700 Subject: [U-Boot] [PATCH] malloc: work around some memalign fragmentation issues In-Reply-To: <20160126095402.1c80368a@amdc2363> References: <1453755822-28569-1-git-send-email-swarren@wwwdotorg.org> <20160126095402.1c80368a@amdc2363> Message-ID: <56A79E56.70202@wwwdotorg.org> List-Id: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: u-boot@lists.denx.de On 01/26/2016 01:54 AM, Lukasz Majewski wrote: > Hi Stephen, > >> From: Stephen Warren >> >> Use of memalign can trigger fragmentation issues such as: >> >> // Internally, this needs to find a free block quite bit larger than >> s. // Once the free region is found, any unaligned "padding" >> immediately // before and after the block is marked free, so that the >> allocation // takes only s bytes (plus malloc header overhead). >> p = memalign(a, s); >> // If there's little fragmentation so far, this allocation is likely >> // located immediately after p. >> p2 = malloc(x); >> free(p); >> // In theory, this should return the same value for p. However, the >> hole // left by the free() call is only s in size (plus malloc header >> overhead) // whereas memalign searches for a larger block in order to >> guarantee it // can adjust the returned pointer to the alignment >> requirements. Hence, // the pointer returned, if any, won't be p. If >> there's little or no space // left after p2, this allocation will >> fail. p = memalign(a, s); >> >> In practice, this issue occurs when running the "dfu" command >> repeatedly on NVIDIA Tegra boards, since DFU allocates a large 32M >> data buffer, and then initializes the USB controller. If this is the >> first time USB has been used in the U-Boot session, this causes a >> probe of the USB driver, which causes various allocations, including >> a strdup() of a GPIO name when requesting the VBUS GPIO. When DFU is >> torn down, the USB driver is left probed, and hence its memory is >> left allocated. If "dfu" is executed again, allocation of the 32M >> data buffer fails as described above. >> >> In practice, there is a memory hole exactly large enough to hold the >> 32M data buffer than DFU needs. However, memalign() can't know that >> in a general way. Given that, it's particularly annoying that the >> allocation fails! >> >> The issue is that memalign() tries to allocate something larger to >> guarantee the ability to align the returned pointer. This patch >> modifies memalign() so that if the "general case" over-sized >> allocation fails, another allocation is attempted, of the exact size >> the user desired. If that allocation just happens to be aligned in >> the way the user wants, (and in the case described above, it will be, >> since the free memory region is located where a previous identical >> allocation was located), the pointer can be returned. >> >> This patch is somewhat related to 806bd245b1ab "dfu: don't keep >> freeing/reallocating". That patch worked around the issue by removing >> repeated free/memalign within a single execution of "dfu". However, >> the same technique can't be applied across multiple invocations, since >> there's no reason to keep the DFU buffer allocated while DFU isn't >> running. This patch addresses the root-cause a bit more directly. >> >> This problem highlights some of the disadvantages of dynamic >> allocation and deferred probing of devices. >> >> 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 >> --- >> common/dlmalloc.c | 22 ++++++++++++++++++++++ >> 1 file changed, 22 insertions(+) >> >> diff --git a/common/dlmalloc.c b/common/dlmalloc.c >> index b5bb05191c24..2b964d16b11e 100644 >> --- a/common/dlmalloc.c >> +++ b/common/dlmalloc.c >> @@ -2829,6 +2829,28 @@ Void_t* mEMALIGn(alignment, bytes) size_t >> alignment; size_t bytes; nb = request2size(bytes); >> m = (char*)(mALLOc(nb + alignment + MINSIZE)); >> >> + /* >> + * The attempt to over-allocate (with a size large enough to >> guarantee the >> + * ability to find an aligned region within allocated memory) >> failed. >> + * >> + * Try again, this time only allocating exactly the size the user >> wants. If >> + * the allocation now succeeds and just happens to be aligned, we >> can still >> + * fulfill the user's request. >> + */ >> + if (m == NULL) { >> + /* >> + * Use bytes not nb, since mALLOc internally calls request2size >> too, and >> + * each call increases the size to allocate, to account for the >> header. >> + */ >> + m = (char*)(mALLOc(bytes)); >> + /* Aligned -> return it */ >> + if ((((unsigned long)(m)) % alignment) == 0) >> + return m; >> + /* Otherwise, fail */ >> + fREe(m); >> + return NULL; >> + } >> + >> if (m == NULL) return NULL; /* propagate failure */ >> >> p = mem2chunk(m); > > U-boot's ./common/dlmalloc.c file is from year 2000 (version 2.6.6). > I'm just wondering if there exists newer version of this code (and can > be easily ported to u-boot). There certainly are newer versions: http://gee.cs.oswego.edu/dl/html/malloc.html The changelog in the source doesn't appear to address issues such as this one. Equally, a very brief inspection of the latest implementation of memalign() seems like it would suffer from the same issue. I don't know if there are any other internal changes (e.g. perhaps bucketing free areas by size/alignment or similar) that might avoid the issue.