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

Joey Ye joey.ye.cc@gmail.com
Tue Jan 10 03:46:00 GMT 2017


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



More information about the Newlib mailing list