public inbox for newlib@sourceware.org
 help / color / mirror / Atom feed
From: Jerome Leroux <jerome.leroux@microej.com>
To: newlib@sourceware.org
Subject: Malloc: unusable area at the end of the heap section
Date: Mon, 6 Jun 2022 17:17:55 -0400	[thread overview]
Message-ID: <c05ce6e8-e618-7035-6c58-b3ea7204678a@microej.com> (raw)

Hello Newlib developers,

I am a user of Newlib in a project that runs on an NXP MCU.
I am using MCUXpressoIDE_11.3.0_5180_prc3, which comes with GCC “arm-none-eabi-gcc.exe (GNU Arm Embedded Toolchain 
9-2020-q2-update) 9.3.1 20200408 (release)” and Newlib 3.3.0.

I have identified an issue in malloc, and I think the problem is still present in the latest version of Newlib. I could 
not see any changes in the incriminated code since Newlib 3.3.0.

I noticed this issue only in the standard malloc implementation and not in the nano-malloc version.

Here is a description of the problem:
The allocator splits the heap into pages. When a page is full, it increases the heap size by reserving a new page in the 
heap section. When reserving a new page, the allocator keeps the page end address aligned with malloc_getpagesize, which 
is set to 4096 by default. If there is not enough space to reserve the full page, the allocation fails even if there is 
enough space in the heap to allocate the chunk of memory.
Because the issue is related to the heap end address and how the linker positions the heap, the same sequence of 
allocations may lead to different results (failure or success) depending on the location of the heap, even if the heap 
size is constant. Typically, adding a new C global variable can shift the start address of the heap section and cause a 
malloc error.

For example, with a heap section of 4096 bytes (0x1000 bytes):
If the heap section address is 0x20100-0x21100, during the initialization, the page end address is set to 0x21000 
(aligned on 4096). We will be able to allocate until the address 0x21000. After that, the allocator will try to reserve 
a new page, but it will fail because it won’t be able to reserve a 4096 bytes page from 0x21000 to 0x22000. The 
following allocations will fail. The usable heap size is 3840 bytes (0x21000 - 0x20100) instead of 4096.
If the heap section address is 0x20F00-0x21F00 (same size), with the same scenario, the usable heap size is 256 bytes 
(0x21000 - 0x20F00).
Here are two examples of heap configurations: 
https://gist.github.com/jerome-leroux/759159fbd3e7bb5e189dbceb04636914?permalink_comment_id=4191266#gistcomment-4191266

I did not dig into the implementation so much. From my understanding, the problem comes from the usage of 
"malloc_getpagesize" (see 
https://github.com/bminor/newlib/blob/830a9b707caa5e343b6ffce7fcb2d3ca97e3259c/newlib/libc/stdlib/_mallocr.c#L198) in 
"malloc_extend_top" (probably here 
https://github.com/bminor/newlib/blob/830a9b707caa5e343b6ffce7fcb2d3ca97e3259c/newlib/libc/stdlib/_mallocr.c#L2166).
I can understand it makes sense to keep the pages aligned when running in a system that implements virtual memory. 
Still, on an MCU, the heap is just a contiguous chunk of memory allocated at link time. Furthermore, the heap size is 
usually pretty small (a few kilobytes), so potentially wasting 4 KB of memory is unacceptable. Using the default 
implementation of "sbrk" documented at https://sourceware.org/newlib/libc.html#index-sbrk will lead to the problem.

I have written a simple example that demonstrates the issue (see 
https://gist.github.com/jerome-leroux/759159fbd3e7bb5e189dbceb04636914 ). To reproduce the problem, define the macros 
HEAP_SECTION_START_SYMBOL and HEAP_SECTION_END_SYMBOL, which are specific to your environment. Then call the function 
"test_malloc()".

I tried to find someone with the same issue, but I couldn’t. The related commits/discussions I found are:
- https://github.com/bminor/newlib/commit/4a3d0a5a5d829c05868a34658eb45731dbb5112b
- https://stackoverflow.com/questions/39088598/malloc-in-newlib-does-it-waste-memory-after-one-big-failure-allocation

Can anyone confirm what I have noticed?

Thanks.

-- 
Jerome Leroux


             reply	other threads:[~2022-06-06 21:17 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-06-06 21:17 Jerome Leroux [this message]
2022-06-07  6:17 ` Torbjorn SVENSSON
2022-06-07 16:03   ` Jeff Johnston
2022-06-07 16:38     ` Torbjorn SVENSSON

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=c05ce6e8-e618-7035-6c58-b3ea7204678a@microej.com \
    --to=jerome.leroux@microej.com \
    --cc=newlib@sourceware.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).