[PATCH 1/2] Used chunk needs to be removed from free_list

[PATCH 1/2] Used chunk needs to be removed from free_list

[Torbjörn SVENSSON]

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

[PATCH 1/2] Used chunk needs to be removed from free_list

[Torbjörn SVENSSON]

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

[PATCH 2/2] Don't allocate another header when merging chunks

[Torbjörn SVENSSON]

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 2/2] Don't allocate another header when merging chunks

[Torbjörn SVENSSON]

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

Re: [PATCH 2/2] Don't allocate another header when merging chunks

[Jeff Johnston]

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
>
>

Re: [PATCH 2/2] Don't allocate another header when merging chunks

[Torbjorn SVENSSON]

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
> 

Re: [PATCH 2/2] Don't allocate another header when merging chunks

[Jeff Johnston]

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
> >
>
>

Re: [PATCH 2/2] Don't allocate another header when merging chunks

[Jeff Johnston]

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
>
>

Re: [PATCH 1/2] Used chunk needs to be removed from free_list

[Jeff Johnston]

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
>
>