[PATCH 2/2] Fix padding initialization in nano_malloc?

[PATCH 2/2] Fix padding initialization in nano_malloc?

[Joe Seymour]

While working on another issue, I noticed something in nano-mallocr.c
that doesn't look right to me:

As described in nano-mallocr.c, chunks of heap are represented in memory
as follows: [ size ] [ optional padding ] [ data area ]

Note that "optional padding" refers to padding added explicitly by code,
not to any padding that the compiler could theoretically introduce into
the layout of the struct.

Annotating the code around line 310 of nano-mallocr.c (nano_malloc) with
some comments:

    /* r is either a chunk address retrieved from the free list, or a
       new address retrieved from sbrk_aligned.  */

    /* ptr points to the data area ASSUMING that no optional padding is
       being used.  */
    ptr = (char *)r + CHUNK_OFFSET;

    /* align_ptr points to the data area, taking any padding into
       account.  */
    align_ptr = (char *)ALIGN_TO((unsigned long)ptr, MALLOC_ALIGN);

    /* offset is the size of the optional padding.  */
    offset = align_ptr - ptr;

This means that r < ptr <= align_ptr

The layout can then be summarised as follows:
  (r) [ size ] [ compiler padding ]
  (ptr) [ explicit optional padding ]
  (align_ptr) [ data area ]

nano_malloc then needs to initialize any optional padding with a
negative offset to size:

    if (offset)
    {
      *(long *)((char *)r + offset) = -offset;
    }

The above code calculates the address of the optional padding as
(r + offset).  This looks incorrect to me, as offset is the size of the
padding, not the size of [ size ] + [ compiler padding ].

Similarly, it then populates the padding with -offset, when the padding
should be populated with a negative offset to [ size ].

I don't have a motivating test case for this, it is based purely on
reading of the code. I suspect that in most (all?) real cases the value
of offset is coincidentally equal to the required value.

The following patch addresses these concerns.

I've built and tested as follows:
  Configured (gcc+newlib) with: --target=msp430-elf --enable-languages=c
  gcc testsuite variations:
    msp430-sim/-mcpu=msp430
    msp430-sim/-mcpu=msp430x
    msp430-sim/-mcpu=msp430x/-mlarge/-mdata-region=either/-mcode-region=either
    msp430-sim/-mhwmult=none
    msp430-sim/-mhwmult=f5series
My testing has shown no regressions, however I don't know if the gcc
testsuite provides sufficient coverage for this patch?

In an ideal world I would propose a patch that eliminates the use of
code-managed padding in nano_malloc, unfortunately I don't have the time
to consider whether such a patch is viable.

I don't have write access, so if this patch is deemed correct and
acceptable, I would appreciate if someone would commit it on my behalf.

Thanks,

2017-01-XX  Joe Seymour  <joe.s@somniumtech.com>

	newlib/
	* libc/stdlib/nano-mallocr.c (nano_malloc): Fix initialization
	of padding. Add comments.
	(nano_memalign): Fix initialization of padding.
---
 newlib/libc/stdlib/nano-mallocr.c |    9 +++++++--
 1 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
index 457eb88..61e6591 100644
--- a/newlib/libc/stdlib/nano-mallocr.c
+++ b/newlib/libc/stdlib/nano-mallocr.c
@@ -307,14 +307,19 @@ void * nano_malloc(RARG malloc_size_t s)
     }
     MALLOC_UNLOCK;
 
+    /* ptr points to malloc_chunk.next, ASSUMING that no alignment padding is
+       being used.  */
     ptr = (char *)r + CHUNK_OFFSET;
 
+    /* align_ptr points to malloc_chunk.next, taking alignment padding into
+       account.  */
     align_ptr = (char *)ALIGN_TO((unsigned long)ptr, MALLOC_ALIGN);
     offset = align_ptr - ptr;
 
     if (offset)
     {
-        *(long *)((char *)r + offset) = -offset;
+        /* Write the negative offset to size into alignment padding.  */
+        *(long *)(ptr) = -(CHUNK_OFFSET);
     }
 
     assert(align_ptr + size <= (char *)r + alloc_size);
@@ -587,7 +592,7 @@ void * nano_memalign(RARG size_t align, size_t s)
             /* Padding is used. Need to set a jump offset for aligned pointer
             * to get back to chunk head */
             assert(offset >= sizeof(int));
-            *(long *)((char *)chunk_p + offset) = -offset;
+            *(long *)((char *)chunk_p + CHUNK_OFFSET) = -(CHUNK_OFFSET);
         }
     }
 
-- 
1.7.1

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Corinna Vinschen]

[-- Attachment #1: Type: text/plain, Size: 4801 bytes --]

Joey?  Bin?

Any input?


Thanks,
Corinna

On Jan  3 14:56, Joe Seymour wrote:
> While working on another issue, I noticed something in nano-mallocr.c
> that doesn't look right to me:
> 
> As described in nano-mallocr.c, chunks of heap are represented in memory
> as follows: [ size ] [ optional padding ] [ data area ]
> 
> Note that "optional padding" refers to padding added explicitly by code,
> not to any padding that the compiler could theoretically introduce into
> the layout of the struct.
> 
> Annotating the code around line 310 of nano-mallocr.c (nano_malloc) with
> some comments:
> 
>     /* r is either a chunk address retrieved from the free list, or a
>        new address retrieved from sbrk_aligned.  */
> 
>     /* ptr points to the data area ASSUMING that no optional padding is
>        being used.  */
>     ptr = (char *)r + CHUNK_OFFSET;
> 
>     /* align_ptr points to the data area, taking any padding into
>        account.  */
>     align_ptr = (char *)ALIGN_TO((unsigned long)ptr, MALLOC_ALIGN);
> 
>     /* offset is the size of the optional padding.  */
>     offset = align_ptr - ptr;
> 
> This means that r < ptr <= align_ptr
> 
> The layout can then be summarised as follows:
>   (r) [ size ] [ compiler padding ]
>   (ptr) [ explicit optional padding ]
>   (align_ptr) [ data area ]
> 
> nano_malloc then needs to initialize any optional padding with a
> negative offset to size:
> 
>     if (offset)
>     {
>       *(long *)((char *)r + offset) = -offset;
>     }
> 
> The above code calculates the address of the optional padding as
> (r + offset).  This looks incorrect to me, as offset is the size of the
> padding, not the size of [ size ] + [ compiler padding ].
> 
> Similarly, it then populates the padding with -offset, when the padding
> should be populated with a negative offset to [ size ].
> 
> I don't have a motivating test case for this, it is based purely on
> reading of the code. I suspect that in most (all?) real cases the value
> of offset is coincidentally equal to the required value.
> 
> The following patch addresses these concerns.
> 
> I've built and tested as follows:
>   Configured (gcc+newlib) with: --target=msp430-elf --enable-languages=c
>   gcc testsuite variations:
>     msp430-sim/-mcpu=msp430
>     msp430-sim/-mcpu=msp430x
>     msp430-sim/-mcpu=msp430x/-mlarge/-mdata-region=either/-mcode-region=either
>     msp430-sim/-mhwmult=none
>     msp430-sim/-mhwmult=f5series
> My testing has shown no regressions, however I don't know if the gcc
> testsuite provides sufficient coverage for this patch?
> 
> In an ideal world I would propose a patch that eliminates the use of
> code-managed padding in nano_malloc, unfortunately I don't have the time
> to consider whether such a patch is viable.
> 
> I don't have write access, so if this patch is deemed correct and
> acceptable, I would appreciate if someone would commit it on my behalf.
> 
> Thanks,
> 
> 2017-01-XX  Joe Seymour  <joe.s@somniumtech.com>
> 
> 	newlib/
> 	* libc/stdlib/nano-mallocr.c (nano_malloc): Fix initialization
> 	of padding. Add comments.
> 	(nano_memalign): Fix initialization of padding.
> ---
>  newlib/libc/stdlib/nano-mallocr.c |    9 +++++++--
>  1 files changed, 7 insertions(+), 2 deletions(-)
> 
> diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
> index 457eb88..61e6591 100644
> --- a/newlib/libc/stdlib/nano-mallocr.c
> +++ b/newlib/libc/stdlib/nano-mallocr.c
> @@ -307,14 +307,19 @@ void * nano_malloc(RARG malloc_size_t s)
>      }
>      MALLOC_UNLOCK;
>  
> +    /* ptr points to malloc_chunk.next, ASSUMING that no alignment padding is
> +       being used.  */
>      ptr = (char *)r + CHUNK_OFFSET;
>  
> +    /* align_ptr points to malloc_chunk.next, taking alignment padding into
> +       account.  */
>      align_ptr = (char *)ALIGN_TO((unsigned long)ptr, MALLOC_ALIGN);
>      offset = align_ptr - ptr;
>  
>      if (offset)
>      {
> -        *(long *)((char *)r + offset) = -offset;
> +        /* Write the negative offset to size into alignment padding.  */
> +        *(long *)(ptr) = -(CHUNK_OFFSET);
>      }
>  
>      assert(align_ptr + size <= (char *)r + alloc_size);
> @@ -587,7 +592,7 @@ void * nano_memalign(RARG size_t align, size_t s)
>              /* Padding is used. Need to set a jump offset for aligned pointer
>              * to get back to chunk head */
>              assert(offset >= sizeof(int));
> -            *(long *)((char *)chunk_p + offset) = -offset;
> +            *(long *)((char *)chunk_p + CHUNK_OFFSET) = -(CHUNK_OFFSET);
>          }
>      }
>  
> -- 
> 1.7.1

-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Joey Ye]

Joe,

Thanks for reading the code and starting this discussion. But IMHO you
misunderstood the data structure thus this patch is not valid.

ptr includes the compiler inserted padding, as it is r+CHUNK_OFFSET.
align_ptr include both compiler inserted padding and explicit optional
padding. Please be remember that padding are inclusive, which means
the bigger padding include smaller padding instead of adding on top of
bigger padding.

About the offset, it is used to redirect to head of the chunk when
looking from chunk from data pointer. Normally get_chunk_from_ptr will
get the head of the chunk by data_pointer-CHUNK_OFFSET, or
align_ptr-CHUNK_OFFSET looking from malloc's point of view. So
align_ptr - CHUNK_OFFSET should be stored with the negative offset.
Due to following deduction, the address was calculated with r +
offset. In you patch saving nagive offset to *ptr will make the
negative offset unaddressable in get_chunk_from_ptr, as ptr itself is
only addressable from r, not from align_ptr.

align_ptr = ptr + offset
ptr = r + CHUNK_OFFSET
=> align_ptr-CHUNK_OFFSET = r + offset

Following picture shows the detail layout when optional padding is
needed. The arrows on the right shows how get_chunk_from_ptr works
(copy/paste to a fixed size font editor to read it decently):

    /*          ------------------
     *       r->| size (4 bytes) |<-------
     *          ------------------       |
     *          |Compiler Padding|       |
     *          ------------------       |
     *     ptr->|r + CHUNK_OFFSET|       | align_ptr - CHUNK_OFFSET - offset
     *          ------------------       |
     *          |explicit padding|       |
     *          |size = offset   |       |
     *          | ...            |       |
     *r+offset->| -offset        |<--  ---
     *          | ...            |  | align_ptr - CHUNK_OFFSET
     *          ------------------  |
     align_ptr->| data pointer   | --

Though I maybe wrong as the code was written years ago and it took me
a while to recall the logic. Your further comments is appreciated.

Thanks,
Joey

On Mon, Jan 9, 2017 at 3:19 PM, Corinna Vinschen <vinschen@redhat.com> wrote:
> Joey?  Bin?
>
> Any input?
>
>
> Thanks,
> Corinna
>
> On Jan  3 14:56, Joe Seymour wrote:
>> While working on another issue, I noticed something in nano-mallocr.c
>> that doesn't look right to me:
>>
>> As described in nano-mallocr.c, chunks of heap are represented in memory
>> as follows: [ size ] [ optional padding ] [ data area ]
>>
>> Note that "optional padding" refers to padding added explicitly by code,
>> not to any padding that the compiler could theoretically introduce into
>> the layout of the struct.
>>
>> Annotating the code around line 310 of nano-mallocr.c (nano_malloc) with
>> some comments:
>>
>>     /* r is either a chunk address retrieved from the free list, or a
>>        new address retrieved from sbrk_aligned.  */
>>
>>     /* ptr points to the data area ASSUMING that no optional padding is
>>        being used.  */
>>     ptr = (char *)r + CHUNK_OFFSET;
>>
>>     /* align_ptr points to the data area, taking any padding into
>>        account.  */
>>     align_ptr = (char *)ALIGN_TO((unsigned long)ptr, MALLOC_ALIGN);
>>
>>     /* offset is the size of the optional padding.  */
>>     offset = align_ptr - ptr;
>>
>> This means that r < ptr <= align_ptr
>>
>> The layout can then be summarised as follows:
>>   (r) [ size ] [ compiler padding ]
>>   (ptr) [ explicit optional padding ]
>>   (align_ptr) [ data area ]
>>
>> nano_malloc then needs to initialize any optional padding with a
>> negative offset to size:
>>
>>     if (offset)
>>     {
>>       *(long *)((char *)r + offset) = -offset;
>>     }
>>
>> The above code calculates the address of the optional padding as
>> (r + offset).  This looks incorrect to me, as offset is the size of the
>> padding, not the size of [ size ] + [ compiler padding ].
>>
>> Similarly, it then populates the padding with -offset, when the padding
>> should be populated with a negative offset to [ size ].
>>
>> I don't have a motivating test case for this, it is based purely on
>> reading of the code. I suspect that in most (all?) real cases the value
>> of offset is coincidentally equal to the required value.
>>
>> The following patch addresses these concerns.
>>
>> I've built and tested as follows:
>>   Configured (gcc+newlib) with: --target=msp430-elf --enable-languages=c
>>   gcc testsuite variations:
>>     msp430-sim/-mcpu=msp430
>>     msp430-sim/-mcpu=msp430x
>>     msp430-sim/-mcpu=msp430x/-mlarge/-mdata-region=either/-mcode-region=either
>>     msp430-sim/-mhwmult=none
>>     msp430-sim/-mhwmult=f5series
>> My testing has shown no regressions, however I don't know if the gcc
>> testsuite provides sufficient coverage for this patch?
>>
>> In an ideal world I would propose a patch that eliminates the use of
>> code-managed padding in nano_malloc, unfortunately I don't have the time
>> to consider whether such a patch is viable.
>>
>> I don't have write access, so if this patch is deemed correct and
>> acceptable, I would appreciate if someone would commit it on my behalf.
>>
>> Thanks,
>>
>> 2017-01-XX  Joe Seymour  <joe.s@somniumtech.com>
>>
>>       newlib/
>>       * libc/stdlib/nano-mallocr.c (nano_malloc): Fix initialization
>>       of padding. Add comments.
>>       (nano_memalign): Fix initialization of padding.
>> ---
>>  newlib/libc/stdlib/nano-mallocr.c |    9 +++++++--
>>  1 files changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
>> index 457eb88..61e6591 100644
>> --- a/newlib/libc/stdlib/nano-mallocr.c
>> +++ b/newlib/libc/stdlib/nano-mallocr.c
>> @@ -307,14 +307,19 @@ void * nano_malloc(RARG malloc_size_t s)
>>      }
>>      MALLOC_UNLOCK;
>>
>> +    /* ptr points to malloc_chunk.next, ASSUMING that no alignment padding is
>> +       being used.  */
>>      ptr = (char *)r + CHUNK_OFFSET;
>>
>> +    /* align_ptr points to malloc_chunk.next, taking alignment padding into
>> +       account.  */
>>      align_ptr = (char *)ALIGN_TO((unsigned long)ptr, MALLOC_ALIGN);
>>      offset = align_ptr - ptr;
>>
>>      if (offset)
>>      {
>> -        *(long *)((char *)r + offset) = -offset;
>> +        /* Write the negative offset to size into alignment padding.  */
>> +        *(long *)(ptr) = -(CHUNK_OFFSET);
>>      }
>>
>>      assert(align_ptr + size <= (char *)r + alloc_size);
>> @@ -587,7 +592,7 @@ void * nano_memalign(RARG size_t align, size_t s)
>>              /* Padding is used. Need to set a jump offset for aligned pointer
>>              * to get back to chunk head */
>>              assert(offset >= sizeof(int));
>> -            *(long *)((char *)chunk_p + offset) = -offset;
>> +            *(long *)((char *)chunk_p + CHUNK_OFFSET) = -(CHUNK_OFFSET);
>>          }
>>      }
>>
>> --
>> 1.7.1
>
> --
> Corinna Vinschen
> Cygwin Maintainer
> Red Hat

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Joe Seymour]

Hi Joey,

On 10/01/2017 03:45, Joey Ye wrote:
> Thanks for reading the code and starting this discussion. But IMHO you
> misunderstood the data structure thus this patch is not valid.

Thanks for the review! I agree and withdraw that patch.

I was thinking of the padding as being like a variable-length field in the
structure, which led me to assume that the offset was being read/written from
the beginning of the padding, instead of the end.

To try and stop anyone else making the same mistake I've prepared the following
patch, which adds some more comments to nano-mallocr.c. Note that I haven't
verified that the existing code ensures that the size of padding is at least
CHUNK_OFFSET.

What do you think?

Thanks,

Joe Seymour

---
 newlib/libc/stdlib/nano-mallocr.c |   23 ++++++++++++++++++++---
 1 files changed, 20 insertions(+), 3 deletions(-)

diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
index 457eb88..4497eb6 100644
--- a/newlib/libc/stdlib/nano-mallocr.c
+++ b/newlib/libc/stdlib/nano-mallocr.c
@@ -128,7 +128,7 @@ typedef struct malloc_chunk
      *          ------------------
      *          | Padding for    |
      *          | alignment      |
-     *          | holding neg    |
+     *          | ending with neg|
      *          | offset to size |
      *          ------------------
      * mem_ptr->| point to next  |
@@ -187,9 +187,23 @@ extern void * nano_pvalloc(RARG size_t s);
 
 static inline chunk * get_chunk_from_ptr(void * ptr)
 {
+    /* Assume that there is no explicit padding in the
+       chunk, and that the chunk starts at ptr - CHUNK_OFFSET.  */
     chunk * c = (chunk *)((char *)ptr - CHUNK_OFFSET);
-    /* Skip the padding area */
-    if (c->size < 0) c = (chunk *)((char *)c + c->size);
+
+    if (c->size < 0) {
+      /* c->size being negative indicates that there is explicit padding in
+         the chunk; c->size is actually the last CHUNK_OFFSET bytes in that
+         padding.
+
+         To find the true start of the chunk we need to subtract the size of
+         any remaining padding, and then CHUNK_OFFSET from c.  This is
+         equivalent to subtracting the total size of the padding from c,
+         because the size of any remaining padding is the total size of the
+         padding minus CHUNK_OFFSET.  The end of the padding should have been
+         initialized with this negative offset.  */
+      c = (chunk *)((char *)c + c->size);
+    }
     return c;
 }
 
@@ -314,6 +328,9 @@ void * nano_malloc(RARG malloc_size_t s)
 
     if (offset)
     {
+        /* Initialize the end of the padding with a negative offset to the
+           start of the chunk.  The rest of the padding is not initialized.
+           Note that the size of the padding must be at least CHUNK_OFFSET.  */
         *(long *)((char *)r + offset) = -offset;
     }
 
-- 
1.7.1

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Joey Ye]

Joe,

Thanks for this enhancement to the comments, which is clearer than the original.

Only a minor issue to me: restrictly c->size should be the next word
after the padding, instead of the last word of the padding. After
correcting this problem I am OK with the patch.

Thanks,
Joey

On Wed, Jan 11, 2017 at 2:57 PM, Joe Seymour <joe.s@somniumtech.com> wrote:
> Hi Joey,
>
> On 10/01/2017 03:45, Joey Ye wrote:
>> Thanks for reading the code and starting this discussion. But IMHO you
>> misunderstood the data structure thus this patch is not valid.
>
> Thanks for the review! I agree and withdraw that patch.
>
> I was thinking of the padding as being like a variable-length field in the
> structure, which led me to assume that the offset was being read/written from
> the beginning of the padding, instead of the end.
>
> To try and stop anyone else making the same mistake I've prepared the following
> patch, which adds some more comments to nano-mallocr.c. Note that I haven't
> verified that the existing code ensures that the size of padding is at least
> CHUNK_OFFSET.
>
> What do you think?
>
> Thanks,
>
> Joe Seymour
>
> ---
>  newlib/libc/stdlib/nano-mallocr.c |   23 ++++++++++++++++++++---
>  1 files changed, 20 insertions(+), 3 deletions(-)
>
> diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
> index 457eb88..4497eb6 100644
> --- a/newlib/libc/stdlib/nano-mallocr.c
> +++ b/newlib/libc/stdlib/nano-mallocr.c
> @@ -128,7 +128,7 @@ typedef struct malloc_chunk
>       *          ------------------
>       *          | Padding for    |
>       *          | alignment      |
> -     *          | holding neg    |
> +     *          | ending with neg|
>       *          | offset to size |
>       *          ------------------
>       * mem_ptr->| point to next  |
> @@ -187,9 +187,23 @@ extern void * nano_pvalloc(RARG size_t s);
>
>  static inline chunk * get_chunk_from_ptr(void * ptr)
>  {
> +    /* Assume that there is no explicit padding in the
> +       chunk, and that the chunk starts at ptr - CHUNK_OFFSET.  */
>      chunk * c = (chunk *)((char *)ptr - CHUNK_OFFSET);
> -    /* Skip the padding area */
> -    if (c->size < 0) c = (chunk *)((char *)c + c->size);
> +
> +    if (c->size < 0) {
> +      /* c->size being negative indicates that there is explicit padding in
> +         the chunk; c->size is actually the last CHUNK_OFFSET bytes in that
> +         padding.
> +
> +         To find the true start of the chunk we need to subtract the size of
> +         any remaining padding, and then CHUNK_OFFSET from c.  This is
> +         equivalent to subtracting the total size of the padding from c,
> +         because the size of any remaining padding is the total size of the
> +         padding minus CHUNK_OFFSET.  The end of the padding should have been
> +         initialized with this negative offset.  */
> +      c = (chunk *)((char *)c + c->size);
> +    }
>      return c;
>  }
>
> @@ -314,6 +328,9 @@ void * nano_malloc(RARG malloc_size_t s)
>
>      if (offset)
>      {
> +        /* Initialize the end of the padding with a negative offset to the
> +           start of the chunk.  The rest of the padding is not initialized.
> +           Note that the size of the padding must be at least CHUNK_OFFSET.  */
>          *(long *)((char *)r + offset) = -offset;
>      }
>
> --
> 1.7.1

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Joe Seymour]

On 12/01/2017 02:24, Joey Ye wrote:
> Thanks for this enhancement to the comments, which is clearer than the original.
> 
> Only a minor issue to me: restrictly c->size should be the next word
> after the padding, instead of the last word of the padding. After
> correcting this problem I am OK with the patch.

I'm having a hard time understanding what you mean by this? Would you mind
pointing out (or changing) the sentence or sentences that you'd like changed?

I would avoid referring to the "{last,next} word", because that makes
assumptions about the value of CHUNK_OFFSET. For example, if the type of size
were changed to short, would it still definitely be a word?

Thanks,

Joe

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Joe Seymour]

On 13/01/2017 09:02, Joey Ye wrote:
> My main concern on your comment patch is regard "end of the padding is
> initialized with the negative offset". Actually the negative offset is
> not necessarily the end of all paddings. Although it might happen to
> be if no padding is needed to align chunk->next. What's possibly
> between negative offset and align_ptr is the padding compiler inserted
> to align the structure member "next". Please refer to the picture in
> my initial response.
> 
> I'd suggest to modify the patch in the following way:
>       *          ------------------
>       *          | Padding for    |
>       *          | alignment      |
> -     *          | holding neg    |
> +     *          | ending with neg|
>       *          | offset to size |
>       *          ------------------
> +    *          | Padding to     |
> +    *          | naturally align|
> +    *          | next field        |
> +    *          ---------------------

Thanks for the explanation. I think it depends whether you think of the
compiler padding as coming before or after the explicit padding, and at
different times it makes sense to think of it in different ways.

Your original picture seems to show compiler padding before the explicit
padding (which is how I think of it, because CHUNK_OFFSET = sizeof (size) +
compiler padding), however when reading the padding using c->size we have to
think of the compiler padding as being after the explicit padding.

What do you think of the following patch? It is hopefully more precise. It also
has the advantage that more of the explanation is near the place that I
erroneously tried to patch (at the start of this thread).

Thanks,

Joe Seymour

---
 newlib/libc/stdlib/nano-mallocr.c |   51 ++++++++++++++++++++++++++----------
 1 files changed, 37 insertions(+), 14 deletions(-)

diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
index 457eb88..a0accdd 100644
--- a/newlib/libc/stdlib/nano-mallocr.c
+++ b/newlib/libc/stdlib/nano-mallocr.c
@@ -123,19 +123,24 @@ typedef size_t malloc_size_t;
 
 typedef struct malloc_chunk
 {
-    /*          ------------------
-     *   chunk->| size (4 bytes) |
-     *          ------------------
-     *          | Padding for    |
-     *          | alignment      |
-     *          | holding neg    |
-     *          | offset to size |
-     *          ------------------
-     * mem_ptr->| point to next  |
-     *          | free when freed|
-     *          | or data load   |
-     *          | when allocated |
-     *          ------------------
+    /*          --------------------------------------
+     *   chunk->| size                               |
+     *          --------------------------------------
+     *          | Padding for alignment              |
+     *          | This includes padding inserted by  |
+     *          | the compiler (to align fields) and |
+     *          | explicit padding inserted by this  |
+     *          | implementation. If any explicit    |
+     *          | padding is being used then the     |
+     *          | sizeof (size) bytes at             |
+     *          | mem_ptr - CHUNK_OFFSET must be     |
+     *          | initialized with the negative      |
+     *          | offset to size.                    |
+     *          --------------------------------------
+     * mem_ptr->| When allocated: data               |
+     *          | When freed: pointer to next free   |
+     *          | chunk                              |
+     *          --------------------------------------
      */
     /* size of the allocated payload area, including size before
        CHUNK_OFFSET */
@@ -187,8 +192,13 @@ extern void * nano_pvalloc(RARG size_t s);
 
 static inline chunk * get_chunk_from_ptr(void * ptr)
 {
+    /* Assume that there is no explicit padding in the
+       chunk, and that the chunk starts at ptr - CHUNK_OFFSET.  */
     chunk * c = (chunk *)((char *)ptr - CHUNK_OFFSET);
-    /* Skip the padding area */
+
+    /* c->size being negative indicates that there is explicit padding in
+       the chunk. In which case, c->size is currently the negative offset to
+       the true size.  */
     if (c->size < 0) c = (chunk *)((char *)c + c->size);
     return c;
 }
@@ -314,6 +324,19 @@ void * nano_malloc(RARG malloc_size_t s)
 
     if (offset)
     {
+        /* Initialize sizeof (malloc_chunk.size) bytes at
+           align_ptr - CHUNK_OFFSET with negative offset to the
+           size field (at the start of the chunk).
+
+           The negative offset to size from align_ptr - CHUNK_OFFSET is
+           the size of any remaining padding minus CHUNK_OFFSET.  This is
+           equivalent to the total size of the padding, because the size of
+           any remaining padding is the total size of the padding minus
+           CHUNK_OFFSET.
+
+           Note that the size of the padding must be at least CHUNK_OFFSET.
+
+           The rest of the padding is not initialized.  */
         *(long *)((char *)r + offset) = -offset;
     }
 
-- 
1.7.1

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Joe Seymour]

On 13/01/2017 13:45, Joey Ye wrote:
> OK for me

Thanks. Are you able to approve and commit, or do we need to ask Corinna?

Joe

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Corinna Vinschen]

[-- Attachment #1: Type: text/plain, Size: 336 bytes --]

On Jan 13 14:12, Joe Seymour wrote:
> On 13/01/2017 13:45, Joey Ye wrote:
> > OK for me
> 
> Thanks. Are you able to approve and commit, or do we need to ask Corinna?

Can you please create a patch in `git format-patch' format, with a nice
log message?


Thanks,
Corinna

-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [PATCH 2/2] Fix padding initialization in nano_malloc?

[Joe Seymour]

On 13/01/2017 15:02, Corinna Vinschen wrote:
> Can you please create a patch in `git format-patch' format, with a nice
> log message?

Sorry! I overloaded this thread with a new patch.

I've created a pristine thread with git format-patch:

https://sourceware.org/ml/newlib/2017/msg00053.html