When using nano malloc and the remaning heap space is not big enough to fullfill the allocation, malloc will attempt to merge the last chunk in the free list with a new allocation in order to create a bigger chunk. This is successful, but the chunk still remains in the free_list, so any later call to malloc can give out the same region without it first being freed. Possible sequence to verify: void *p1 = malloc(3000); void *p2 = malloc(4000); void *p3 = malloc(5000); void *p4 = malloc(6000); void *p5 = malloc(7000); free(p2); free(p4); void *p6 = malloc(35000); free(p6); void *p7 = malloc(42000); void *p8 = malloc(32000); Without the change, p7 and p8 points to the same address. Requirement, after malloc(35000), there is less than 42000 bytes available on the heap. Contributed by STMicroelectronics Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com> --- newlib/libc/stdlib/nano-mallocr.c | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c index 99ad60dd0..43eb20e07 100644 --- a/newlib/libc/stdlib/nano-mallocr.c +++ b/newlib/libc/stdlib/nano-mallocr.c @@ -336,6 +336,15 @@ void * nano_malloc(RARG malloc_size_t s) if (sbrk_aligned(RCALL alloc_size) != (void *)-1) { p->size += alloc_size; + + /* Remove chunk from free_list */ + r = free_list; + while (r && p != r->next) + { + r = r->next; + } + r->next = NULL; + r = p; } else -- 2.25.1
When using nano malloc and the remaning heap space is not big enough to fullfill the allocation, malloc will attempt to merge the last chunk in the free list with a new allocation in order to create a bigger chunk. This is successful, but the chunk still remains in the free_list, so any later call to malloc can give out the same region without it first being freed. Possible sequence to verify: void *p1 = malloc(3000); void *p2 = malloc(4000); void *p3 = malloc(5000); void *p4 = malloc(6000); void *p5 = malloc(7000); free(p2); free(p4); void *p6 = malloc(35000); free(p6); void *p7 = malloc(42000); void *p8 = malloc(32000); Without the change, p7 and p8 points to the same address. Requirement, after malloc(35000), there is less than 42000 bytes available on the heap. Contributed by STMicroelectronics Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com> --- newlib/libc/stdlib/nano-mallocr.c | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c index 99ad60dd0..43eb20e07 100644 --- a/newlib/libc/stdlib/nano-mallocr.c +++ b/newlib/libc/stdlib/nano-mallocr.c @@ -336,6 +336,15 @@ void * nano_malloc(RARG malloc_size_t s) if (sbrk_aligned(RCALL alloc_size) != (void *)-1) { p->size += alloc_size; + + /* Remove chunk from free_list */ + r = free_list; + while (r && p != r->next) + { + r = r->next; + } + r->next = NULL; + r = p; } else -- 2.25.1
In the nano version of malloc, when the last chunk is to be extended, there is no need to acount for the header again as it's already taken into account in the overall "alloc_size" at the beginning of the function. Contributed by STMicroelectronics Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com> --- newlib/libc/stdlib/nano-mallocr.c | 4 ---- 1 file changed, 4 deletions(-) diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c index 43eb20e07..b2273ba60 100644 --- a/newlib/libc/stdlib/nano-mallocr.c +++ b/newlib/libc/stdlib/nano-mallocr.c @@ -328,10 +328,6 @@ void * nano_malloc(RARG malloc_size_t s) /* The last free item has the heap end as neighbour. * Let's ask for a smaller amount and merge */ alloc_size -= p->size; - alloc_size = ALIGN_SIZE(alloc_size, CHUNK_ALIGN); /* size of aligned data load */ - alloc_size += MALLOC_PADDING; /* padding */ - alloc_size += CHUNK_OFFSET; /* size of chunk head */ - alloc_size = MAX(alloc_size, MALLOC_MINCHUNK); if (sbrk_aligned(RCALL alloc_size) != (void *)-1) { -- 2.25.1
In the nano version of malloc, when the last chunk is to be extended, there is no need to acount for the header again as it's already taken into account in the overall "alloc_size" at the beginning of the function. Contributed by STMicroelectronics Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com> --- newlib/libc/stdlib/nano-mallocr.c | 4 ---- 1 file changed, 4 deletions(-) diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c index 43eb20e07..b2273ba60 100644 --- a/newlib/libc/stdlib/nano-mallocr.c +++ b/newlib/libc/stdlib/nano-mallocr.c @@ -328,10 +328,6 @@ void * nano_malloc(RARG malloc_size_t s) /* The last free item has the heap end as neighbour. * Let's ask for a smaller amount and merge */ alloc_size -= p->size; - alloc_size = ALIGN_SIZE(alloc_size, CHUNK_ALIGN); /* size of aligned data load */ - alloc_size += MALLOC_PADDING; /* padding */ - alloc_size += CHUNK_OFFSET; /* size of chunk head */ - alloc_size = MAX(alloc_size, MALLOC_MINCHUNK); if (sbrk_aligned(RCALL alloc_size) != (void *)-1) { -- 2.25.1
Patch applied. Thanks.
-- Jeff J.
On Tue, Aug 30, 2022 at 9:57 AM Torbjörn SVENSSON <
torbjorn.svensson@foss.st.com> wrote:
> When using nano malloc and the remaning heap space is not big enough to
> fullfill the allocation, malloc will attempt to merge the last chunk in
> the free list with a new allocation in order to create a bigger chunk.
> This is successful, but the chunk still remains in the free_list, so
> any later call to malloc can give out the same region without it first
> being freed.
>
> Possible sequence to verify:
>
> void *p1 = malloc(3000);
> void *p2 = malloc(4000);
> void *p3 = malloc(5000);
> void *p4 = malloc(6000);
> void *p5 = malloc(7000);
> free(p2);
> free(p4);
> void *p6 = malloc(35000);
> free(p6);
> void *p7 = malloc(42000);
> void *p8 = malloc(32000);
>
> Without the change, p7 and p8 points to the same address.
> Requirement, after malloc(35000), there is less than 42000 bytes
> available on the heap.
>
> Contributed by STMicroelectronics
>
> Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com>
> ---
> newlib/libc/stdlib/nano-mallocr.c | 9 +++++++++
> 1 file changed, 9 insertions(+)
>
> diff --git a/newlib/libc/stdlib/nano-mallocr.c
> b/newlib/libc/stdlib/nano-mallocr.c
> index 99ad60dd0..43eb20e07 100644
> --- a/newlib/libc/stdlib/nano-mallocr.c
> +++ b/newlib/libc/stdlib/nano-mallocr.c
> @@ -336,6 +336,15 @@ void * nano_malloc(RARG malloc_size_t s)
> if (sbrk_aligned(RCALL alloc_size) != (void *)-1)
> {
> p->size += alloc_size;
> +
> + /* Remove chunk from free_list */
> + r = free_list;
> + while (r && p != r->next)
> + {
> + r = r->next;
> + }
> + r->next = NULL;
> +
> r = p;
> }
> else
> --
> 2.25.1
>
>
I think that the check for MALLOC_MINCHUNK should still apply. Do you
agree?
-- Jeff J.
On Tue, Aug 30, 2022 at 9:57 AM Torbjörn SVENSSON <
torbjorn.svensson@foss.st.com> wrote:
> In the nano version of malloc, when the last chunk is to be extended,
> there is no need to acount for the header again as it's already taken
> into account in the overall "alloc_size" at the beginning of the
> function.
>
> Contributed by STMicroelectronics
>
> Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com>
> ---
> newlib/libc/stdlib/nano-mallocr.c | 4 ----
> 1 file changed, 4 deletions(-)
>
> diff --git a/newlib/libc/stdlib/nano-mallocr.c
> b/newlib/libc/stdlib/nano-mallocr.c
> index 43eb20e07..b2273ba60 100644
> --- a/newlib/libc/stdlib/nano-mallocr.c
> +++ b/newlib/libc/stdlib/nano-mallocr.c
> @@ -328,10 +328,6 @@ void * nano_malloc(RARG malloc_size_t s)
> /* The last free item has the heap end as neighbour.
> * Let's ask for a smaller amount and merge */
> alloc_size -= p->size;
> - alloc_size = ALIGN_SIZE(alloc_size, CHUNK_ALIGN); /* size
> of aligned data load */
> - alloc_size += MALLOC_PADDING; /* padding */
> - alloc_size += CHUNK_OFFSET; /* size of chunk head */
> - alloc_size = MAX(alloc_size, MALLOC_MINCHUNK);
>
> if (sbrk_aligned(RCALL alloc_size) != (void *)-1)
> {
> --
> 2.25.1
>
>
Hi Jeff,
Thanks for the review.
No, I don't think the MALLOC_MINCHUNK should apply as I think is to
ensure that there is enough room for the chunk header.
/* size of smallest possible chunk. A memory piece smaller than this size
* won't be able to create a chunk */
#define MALLOC_MINCHUNK (CHUNK_OFFSET + MALLOC_PADDING + MALLOC_MINSIZE)
In this particular case, there is already a chunk, but it's a bit too
small to fit the requested size to malloc(). As a result, it should be
the requested size minus the size for the last chunk minus the size of
the chunk header. The remaining number of bytes is the require memory to
create a chunk (user data + chunk header) that is just the right size.
Think of it like this:
If there is enough free heap, then malloc(100) would just call
_sbrk(108) and return that space.
If that area is then free'ed, and a following malloc(200) is called,
then there are 3 scenarios:
a) there is enough free heap, so it will be like returning the space
returned by _sbrk(208).
b) these is not enough free heap, and the last chunk is still in use. In
this case, malloc would return 0 and errno should be ENOMEM.
c) there is not enough free heap, but the last chunk is no used, thus it
could be extended. If the the chunk was 108 bytes including the header,
then _sbrk(200-108) would be needed to create a single chunk that is 200
bytes + 8 bytes for the header.
If you look for the extreme, then the last chunk size could be 1 byte
less than what is requested of malloc, like the scenario above. The last
chunk size is 100 bytes (plus header) and the application calls
malloc(101). Then it would not make sense to apply MALLOC_MINCHUNK, as
that would call _sbrk(MALLOC_MINCHUNK) rather than _sbrk(1). In this
case, wasting MALLOC_MINCHUNK-1 bytes as they will never be access by
the application.
Does this make sense or am I overthinking this?
Kind regards,
Torbjörn
Ps. Header size for a chunk on arm-none-eabi is 8 bytes, for other
targets, the chunk header can be of different size, but I assumed
arm-none-eabi in my comment above to make it more clear.
Ps2. _sbrk and malloc is obviously more complicated than my example
above, but I tried to reduce the complexity to the involved logic for
extending a chunk size.
On 2022-09-01 20:44, Jeff Johnston wrote:
> I think that the check for MALLOC_MINCHUNK should still apply. Do you
> agree?
>
> -- Jeff J.
>
> On Tue, Aug 30, 2022 at 9:57 AM Torbjörn SVENSSON
> <torbjorn.svensson@foss.st.com <mailto:torbjorn.svensson@foss.st.com>>
> wrote:
>
> In the nano version of malloc, when the last chunk is to be extended,
> there is no need to acount for the header again as it's already taken
> into account in the overall "alloc_size" at the beginning of the
> function.
>
> Contributed by STMicroelectronics
>
> Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com
> <mailto:torbjorn.svensson@foss.st.com>>
> ---
> newlib/libc/stdlib/nano-mallocr.c | 4 ----
> 1 file changed, 4 deletions(-)
>
> diff --git a/newlib/libc/stdlib/nano-mallocr.c
> b/newlib/libc/stdlib/nano-mallocr.c
> index 43eb20e07..b2273ba60 100644
> --- a/newlib/libc/stdlib/nano-mallocr.c
> +++ b/newlib/libc/stdlib/nano-mallocr.c
> @@ -328,10 +328,6 @@ void * nano_malloc(RARG malloc_size_t s)
> /* The last free item has the heap end as neighbour.
> * Let's ask for a smaller amount and merge */
> alloc_size -= p->size;
> - alloc_size = ALIGN_SIZE(alloc_size, CHUNK_ALIGN); /*
> size of aligned data load */
> - alloc_size += MALLOC_PADDING; /* padding */
> - alloc_size += CHUNK_OFFSET; /* size of chunk head */
> - alloc_size = MAX(alloc_size, MALLOC_MINCHUNK);
>
> if (sbrk_aligned(RCALL alloc_size) != (void *)-1)
> {
> --
> 2.25.1
>
Hi Torbjorn,
I was wrong. I somehow had it in my head that MINCHUNK would be checking
for a minimal block size.
Please ignore my comment.
-- Jeff j.
On Thu, Sep 1, 2022 at 3:04 PM Torbjorn SVENSSON <
torbjorn.svensson@foss.st.com> wrote:
> Hi Jeff,
>
> Thanks for the review.
>
> No, I don't think the MALLOC_MINCHUNK should apply as I think is to
> ensure that there is enough room for the chunk header.
>
> /* size of smallest possible chunk. A memory piece smaller than this size
> * won't be able to create a chunk */
> #define MALLOC_MINCHUNK (CHUNK_OFFSET + MALLOC_PADDING + MALLOC_MINSIZE)
>
>
> In this particular case, there is already a chunk, but it's a bit too
> small to fit the requested size to malloc(). As a result, it should be
> the requested size minus the size for the last chunk minus the size of
> the chunk header. The remaining number of bytes is the require memory to
> create a chunk (user data + chunk header) that is just the right size.
>
> Think of it like this:
>
> If there is enough free heap, then malloc(100) would just call
> _sbrk(108) and return that space.
>
> If that area is then free'ed, and a following malloc(200) is called,
> then there are 3 scenarios:
>
> a) there is enough free heap, so it will be like returning the space
> returned by _sbrk(208).
>
> b) these is not enough free heap, and the last chunk is still in use. In
> this case, malloc would return 0 and errno should be ENOMEM.
>
> c) there is not enough free heap, but the last chunk is no used, thus it
> could be extended. If the the chunk was 108 bytes including the header,
> then _sbrk(200-108) would be needed to create a single chunk that is 200
> bytes + 8 bytes for the header.
> If you look for the extreme, then the last chunk size could be 1 byte
> less than what is requested of malloc, like the scenario above. The last
> chunk size is 100 bytes (plus header) and the application calls
> malloc(101). Then it would not make sense to apply MALLOC_MINCHUNK, as
> that would call _sbrk(MALLOC_MINCHUNK) rather than _sbrk(1). In this
> case, wasting MALLOC_MINCHUNK-1 bytes as they will never be access by
> the application.
>
>
> Does this make sense or am I overthinking this?
>
> Kind regards,
> Torbjörn
>
> Ps. Header size for a chunk on arm-none-eabi is 8 bytes, for other
> targets, the chunk header can be of different size, but I assumed
> arm-none-eabi in my comment above to make it more clear.
>
> Ps2. _sbrk and malloc is obviously more complicated than my example
> above, but I tried to reduce the complexity to the involved logic for
> extending a chunk size.
>
>
>
>
> On 2022-09-01 20:44, Jeff Johnston wrote:
> > I think that the check for MALLOC_MINCHUNK should still apply. Do you
> > agree?
> >
> > -- Jeff J.
> >
> > On Tue, Aug 30, 2022 at 9:57 AM Torbjörn SVENSSON
> > <torbjorn.svensson@foss.st.com <mailto:torbjorn.svensson@foss.st.com>>
> > wrote:
> >
> > In the nano version of malloc, when the last chunk is to be extended,
> > there is no need to acount for the header again as it's already taken
> > into account in the overall "alloc_size" at the beginning of the
> > function.
> >
> > Contributed by STMicroelectronics
> >
> > Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com
> > <mailto:torbjorn.svensson@foss.st.com>>
> > ---
> > newlib/libc/stdlib/nano-mallocr.c | 4 ----
> > 1 file changed, 4 deletions(-)
> >
> > diff --git a/newlib/libc/stdlib/nano-mallocr.c
> > b/newlib/libc/stdlib/nano-mallocr.c
> > index 43eb20e07..b2273ba60 100644
> > --- a/newlib/libc/stdlib/nano-mallocr.c
> > +++ b/newlib/libc/stdlib/nano-mallocr.c
> > @@ -328,10 +328,6 @@ void * nano_malloc(RARG malloc_size_t s)
> > /* The last free item has the heap end as neighbour.
> > * Let's ask for a smaller amount and merge */
> > alloc_size -= p->size;
> > - alloc_size = ALIGN_SIZE(alloc_size, CHUNK_ALIGN); /*
> > size of aligned data load */
> > - alloc_size += MALLOC_PADDING; /* padding */
> > - alloc_size += CHUNK_OFFSET; /* size of chunk head */
> > - alloc_size = MAX(alloc_size, MALLOC_MINCHUNK);
> >
> > if (sbrk_aligned(RCALL alloc_size) != (void *)-1)
> > {
> > --
> > 2.25.1
> >
>
>
Patch applied. Thanks.
-- Jeff J.
On Tue, Aug 30, 2022 at 9:57 AM Torbjörn SVENSSON <
torbjorn.svensson@foss.st.com> wrote:
> In the nano version of malloc, when the last chunk is to be extended,
> there is no need to acount for the header again as it's already taken
> into account in the overall "alloc_size" at the beginning of the
> function.
>
> Contributed by STMicroelectronics
>
> Signed-off-by: Torbjörn SVENSSON <torbjorn.svensson@foss.st.com>
> ---
> newlib/libc/stdlib/nano-mallocr.c | 4 ----
> 1 file changed, 4 deletions(-)
>
> diff --git a/newlib/libc/stdlib/nano-mallocr.c
> b/newlib/libc/stdlib/nano-mallocr.c
> index 43eb20e07..b2273ba60 100644
> --- a/newlib/libc/stdlib/nano-mallocr.c
> +++ b/newlib/libc/stdlib/nano-mallocr.c
> @@ -328,10 +328,6 @@ void * nano_malloc(RARG malloc_size_t s)
> /* The last free item has the heap end as neighbour.
> * Let's ask for a smaller amount and merge */
> alloc_size -= p->size;
> - alloc_size = ALIGN_SIZE(alloc_size, CHUNK_ALIGN); /* size
> of aligned data load */
> - alloc_size += MALLOC_PADDING; /* padding */
> - alloc_size += CHUNK_OFFSET; /* size of chunk head */
> - alloc_size = MAX(alloc_size, MALLOC_MINCHUNK);
>
> if (sbrk_aligned(RCALL alloc_size) != (void *)-1)
> {
> --
> 2.25.1
>
>