[U-Boot] C99 and dynamic arrays

[U-Boot] C99 and dynamic arrays

[Tom Rini]

On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
> Hi,
>
> Given that we seem to allow C99 features in U-Boot I wonder if it
> would be OK to use dynamic arrays in SPL?
>
> I am trying to replace:
>
> ptr = malloc(size);
>
> with:
>
> char ptr[size];
>
> to avoid use of malloc in SPL. Can I assume that is permitted?

Without knowing the underlying mechanics of how that works, "maybe".
And we already have malloc in SPL thanks to FAT support.

-- 
Tom

[U-Boot] C99 and dynamic arrays

[Måns Rullgård]

Tom Rini <tom.rini@gmail.com> writes:

> On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
>> Hi,
>>
>> Given that we seem to allow C99 features in U-Boot I wonder if it
>> would be OK to use dynamic arrays in SPL?
>>
>> I am trying to replace:
>>
>> ptr = malloc(size);
>>
>> with:
>>
>> char ptr[size];
>>
>> to avoid use of malloc in SPL. Can I assume that is permitted?
>
> Without knowing the underlying mechanics of how that works, "maybe".

How it works depends on the compiler.  Some compilers implement it by
calling malloc().  GCC uses the stack.

Regardless of how they are implemented, variable-length arrays should,
in my opinion, never be used.  There is simply no way they can be used
safely since no mechanism for detecting failure is provided.  If the
requested size is too large, you will silently overflow the stack or end
up with an invalid/null pointer.  In an environment without full memory
protection, errors resulting from this are very hard to track down.

If the size is somehow limited to a safe value, it is more efficient to
simply allocate this maximum size statically.

-- 
M?ns Rullg?rd
mans at mansr.com

[U-Boot] C99 and dynamic arrays

[Simon Glass]

Hi Tom,

On Tue, Mar 12, 2013 at 4:48 PM, Tom Rini <tom.rini@gmail.com> wrote:
> On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
>> Hi,
>>
>> Given that we seem to allow C99 features in U-Boot I wonder if it
>> would be OK to use dynamic arrays in SPL?
>>
>> I am trying to replace:
>>
>> ptr = malloc(size);
>>
>> with:
>>
>> char ptr[size];
>>
>> to avoid use of malloc in SPL. Can I assume that is permitted?
>
> Without knowing the underlying mechanics of how that works, "maybe".
> And we already have malloc in SPL thanks to FAT support.

If you see this patch:

http://patchwork.ozlabs.org/patch/209635/

In the function pow_mod(), I would like to replace:

val = malloc(key->len * sizeof(uint32_t));

with:

uint32_t val[key->len];

malloc() adds at least 1KB, perhaps 2KB.

Regards,
Simon

[U-Boot] C99 and dynamic arrays

[Wolfgang Denk]

Dear Simon Glass,

In message <CAPnjgZ2bSf8-9gw6MweexMUEXDTYNspxth0GA0XN3RpkLO4R8w@mail.gmail.com> you wrote:
>
> >> Given that we seem to allow C99 features in U-Boot I wonder if it
> >> would be OK to use dynamic arrays in SPL?

Strange.  I can see the follow-ups, but I cannot see the original
posting?

> In the function pow_mod(), I would like to replace:
> 
> val = malloc(key->len * sizeof(uint32_t));
> 
> with:
> 
> uint32_t val[key->len];
> 
> malloc() adds at least 1KB, perhaps 2KB.

I think it is perfectly OK to do that.  Actually I think we already do
this in a number of places.

Best regards,

Wolfgang Denk

-- 
DENX Software Engineering GmbH,     MD: Wolfgang Denk & Detlev Zundel
HRB 165235 Munich, Office: Kirchenstr.5, D-82194 Groebenzell, Germany
Phone: (+49)-8142-66989-10 Fax: (+49)-8142-66989-80 Email: wd at denx.de
"The trouble with doing something right the first time is that nobody
appreciates how difficult it was."                        - Walt West

[U-Boot] C99 and dynamic arrays

[Tom Rini]

On Wed, Mar 13, 2013 at 03:41:33AM -0700, Simon Glass wrote:
> Hi Tom,
> 
> On Tue, Mar 12, 2013 at 4:48 PM, Tom Rini <tom.rini@gmail.com> wrote:
> > On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
> >> Hi,
> >>
> >> Given that we seem to allow C99 features in U-Boot I wonder if it
> >> would be OK to use dynamic arrays in SPL?
> >>
> >> I am trying to replace:
> >>
> >> ptr = malloc(size);
> >>
> >> with:
> >>
> >> char ptr[size];
> >>
> >> to avoid use of malloc in SPL. Can I assume that is permitted?
> >
> > Without knowing the underlying mechanics of how that works, "maybe".
> > And we already have malloc in SPL thanks to FAT support.
> 
> If you see this patch:
> 
> http://patchwork.ozlabs.org/patch/209635/
> 
> In the function pow_mod(), I would like to replace:
> 
> val = malloc(key->len * sizeof(uint32_t));
> 
> with:
> 
> uint32_t val[key->len];
> 
> malloc() adds at least 1KB, perhaps 2KB.

Mans' point is pretty good.  If that's unexpectedly large you're
overflowing your stack and those errors suck.  Wolfgang proded me into
writing the HOWTO to see how much stack your SPL is using, worst case
due to how sucky those can be to debug.  Is 1-2KiB something you don't
have to spare in these cases?  Otherwise perhaps going with a static
allocation is the right call here since DDR is up (if you're doing
malloc already it must be..).

-- 
Tom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
URL: <http://lists.denx.de/pipermail/u-boot/attachments/20130313/64b72d4b/attachment.pgp>

[U-Boot] C99 and dynamic arrays

[Simon Glass]

Hi Mans,

On Wed, Mar 13, 2013 at 3:29 AM, M?ns Rullg?rd <mans@mansr.com> wrote:
> Tom Rini <tom.rini@gmail.com> writes:
>
>> On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
>>> Hi,
>>>
>>> Given that we seem to allow C99 features in U-Boot I wonder if it
>>> would be OK to use dynamic arrays in SPL?
>>>
>>> I am trying to replace:
>>>
>>> ptr = malloc(size);
>>>
>>> with:
>>>
>>> char ptr[size];
>>>
>>> to avoid use of malloc in SPL. Can I assume that is permitted?
>>
>> Without knowing the underlying mechanics of how that works, "maybe".
>
> How it works depends on the compiler.  Some compilers implement it by
> calling malloc().  GCC uses the stack.
>
> Regardless of how they are implemented, variable-length arrays should,
> in my opinion, never be used.  There is simply no way they can be used
> safely since no mechanism for detecting failure is provided.  If the
> requested size is too large, you will silently overflow the stack or end
> up with an invalid/null pointer.  In an environment without full memory
> protection, errors resulting from this are very hard to track down.

I suppose we could check the available stack space. However I don't
really see a clear stack bottom in U-Boot - I think it is set up to
grow downwards as much as needed. I can certainly add sanity checks on
the input values.

>
> If the size is somehow limited to a safe value, it is more efficient to
> simply allocate this maximum size statically.

Yes although this does waste BSS.

Regards,
Simon

>
> --
> M?ns Rullg?rd
> mans at mansr.com

[U-Boot] C99 and dynamic arrays

[Måns Rullgård]

Simon Glass <sjg@google.com> writes:

> Hi Mans,
>
> On Wed, Mar 13, 2013 at 3:29 AM, M?ns Rullg?rd <mans@mansr.com> wrote:
>> Tom Rini <tom.rini@gmail.com> writes:
>>
>>> On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
>>>> Hi,
>>>>
>>>> Given that we seem to allow C99 features in U-Boot I wonder if it
>>>> would be OK to use dynamic arrays in SPL?
>>>>
>>>> I am trying to replace:
>>>>
>>>> ptr = malloc(size);
>>>>
>>>> with:
>>>>
>>>> char ptr[size];
>>>>
>>>> to avoid use of malloc in SPL. Can I assume that is permitted?
>>>
>>> Without knowing the underlying mechanics of how that works, "maybe".
>>
>> How it works depends on the compiler.  Some compilers implement it by
>> calling malloc().  GCC uses the stack.
>>
>> Regardless of how they are implemented, variable-length arrays should,
>> in my opinion, never be used.  There is simply no way they can be used
>> safely since no mechanism for detecting failure is provided.  If the
>> requested size is too large, you will silently overflow the stack or end
>> up with an invalid/null pointer.  In an environment without full memory
>> protection, errors resulting from this are very hard to track down.
>
> I suppose we could check the available stack space. However I don't
> really see a clear stack bottom in U-Boot - I think it is set up to
> grow downwards as much as needed. I can certainly add sanity checks on
> the input values.

There is no way to check stack usage from C.

>> If the size is somehow limited to a safe value, it is more efficient to
>> simply allocate this maximum size statically.
>
> Yes although this does waste BSS.

Sorry, I meant a statically sized stack allocation.

-- 
M?ns Rullg?rd
mans at mansr.com

[U-Boot] C99 and dynamic arrays

[Stephen Warren]

On 03/13/2013 12:03 PM, M?ns Rullg?rd wrote:
> Simon Glass <sjg@google.com> writes:
> 
>> Hi Mans,
>>
>> On Wed, Mar 13, 2013 at 3:29 AM, M?ns Rullg?rd <mans@mansr.com> wrote:
>>> Tom Rini <tom.rini@gmail.com> writes:
>>>
>>>> On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
>>>>> Hi,
>>>>>
>>>>> Given that we seem to allow C99 features in U-Boot I wonder if it
>>>>> would be OK to use dynamic arrays in SPL?
>>>>>
>>>>> I am trying to replace:
>>>>>
>>>>> ptr = malloc(size);
>>>>>
>>>>> with:
>>>>>
>>>>> char ptr[size];
>>>>>
>>>>> to avoid use of malloc in SPL. Can I assume that is permitted?
>>>>
>>>> Without knowing the underlying mechanics of how that works, "maybe".
>>>
>>> How it works depends on the compiler.  Some compilers implement it by
>>> calling malloc().  GCC uses the stack.
>>>
>>> Regardless of how they are implemented, variable-length arrays should,
>>> in my opinion, never be used.  There is simply no way they can be used
>>> safely since no mechanism for detecting failure is provided.  If the
>>> requested size is too large, you will silently overflow the stack or end
>>> up with an invalid/null pointer.  In an environment without full memory
>>> protection, errors resulting from this are very hard to track down.
>>
>> I suppose we could check the available stack space. However I don't
>> really see a clear stack bottom in U-Boot - I think it is set up to
>> grow downwards as much as needed. I can certainly add sanity checks on
>> the input values.
> 
> There is no way to check stack usage from C.
> 
>>> If the size is somehow limited to a safe value, it is more efficient to
>>> simply allocate this maximum size statically.
>>
>> Yes although this does waste BSS.
> 
> Sorry, I meant a statically sized stack allocation.

But, there's also no way to detect failure in that case either.

[U-Boot] C99 and dynamic arrays

[Simon Glass]

[once more from correct address, sorry]

Hi,

On Wed, Mar 13, 2013 at 11:03 AM, M?ns Rullg?rd <mans@mansr.com> wrote:
> Simon Glass <sjg@google.com> writes:
>
>> Hi Mans,
>>
>> On Wed, Mar 13, 2013 at 3:29 AM, M?ns Rullg?rd <mans@mansr.com> wrote:
>>> Tom Rini <tom.rini@gmail.com> writes:
>>>
>>>> On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
>>>>> Hi,
>>>>>
>>>>> Given that we seem to allow C99 features in U-Boot I wonder if it
>>>>> would be OK to use dynamic arrays in SPL?
>>>>>
>>>>> I am trying to replace:
>>>>>
>>>>> ptr = malloc(size);
>>>>>
>>>>> with:
>>>>>
>>>>> char ptr[size];
>>>>>
>>>>> to avoid use of malloc in SPL. Can I assume that is permitted?
>>>>
>>>> Without knowing the underlying mechanics of how that works, "maybe".
>>>
>>> How it works depends on the compiler.  Some compilers implement it by
>>> calling malloc().  GCC uses the stack.
>>>
>>> Regardless of how they are implemented, variable-length arrays should,
>>> in my opinion, never be used.  There is simply no way they can be used
>>> safely since no mechanism for detecting failure is provided.  If the
>>> requested size is too large, you will silently overflow the stack or end
>>> up with an invalid/null pointer.  In an environment without full memory
>>> protection, errors resulting from this are very hard to track down.
>>
>> I suppose we could check the available stack space. However I don't
>> really see a clear stack bottom in U-Boot - I think it is set up to
>> grow downwards as much as needed. I can certainly add sanity checks on
>> the input values.
>
> There is no way to check stack usage from C.

Well there is an architecture-specific way. A function can generally
find its own stack pointer by taking the address of a local variable,
so it is possible to write a function to check for stack overflow. We
could add this in U-Boot if it is a general problem. For my purposes
the amount of stack I intend to allocate is fairly small (1-2KB
perhaps).

>
>>> If the size is somehow limited to a safe value, it is more efficient to
>>> simply allocate this maximum size statically.
>>
>> Yes although this does waste BSS.
>
> Sorry, I meant a statically sized stack allocation.

OK, then I suppose this is not much different from dynamic arrays?

>
> --
> M?ns Rullg?rd
> mans at mansr.com

Regards,
Simon

[U-Boot] C99 and dynamic arrays

[Måns Rullgård]

Simon Glass <sjg@chromium.org> writes:

> [once more from correct address, sorry]
>
> Hi,
>
> On Wed, Mar 13, 2013 at 11:03 AM, M?ns Rullg?rd <mans@mansr.com> wrote:
>> Simon Glass <sjg@google.com> writes:
>>
>>> Hi Mans,
>>>
>>> On Wed, Mar 13, 2013 at 3:29 AM, M?ns Rullg?rd <mans@mansr.com> wrote:
>>>> Tom Rini <tom.rini@gmail.com> writes:
>>>>
>>>>> On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
>>>>>> Hi,
>>>>>>
>>>>>> Given that we seem to allow C99 features in U-Boot I wonder if it
>>>>>> would be OK to use dynamic arrays in SPL?
>>>>>>
>>>>>> I am trying to replace:
>>>>>>
>>>>>> ptr = malloc(size);
>>>>>>
>>>>>> with:
>>>>>>
>>>>>> char ptr[size];
>>>>>>
>>>>>> to avoid use of malloc in SPL. Can I assume that is permitted?
>>>>>
>>>>> Without knowing the underlying mechanics of how that works, "maybe".
>>>>
>>>> How it works depends on the compiler.  Some compilers implement it by
>>>> calling malloc().  GCC uses the stack.
>>>>
>>>> Regardless of how they are implemented, variable-length arrays should,
>>>> in my opinion, never be used.  There is simply no way they can be used
>>>> safely since no mechanism for detecting failure is provided.  If the
>>>> requested size is too large, you will silently overflow the stack or end
>>>> up with an invalid/null pointer.  In an environment without full memory
>>>> protection, errors resulting from this are very hard to track down.
>>>
>>> I suppose we could check the available stack space. However I don't
>>> really see a clear stack bottom in U-Boot - I think it is set up to
>>> grow downwards as much as needed. I can certainly add sanity checks on
>>> the input values.
>>
>> There is no way to check stack usage from C.
>
> Well there is an architecture-specific way. A function can generally
> find its own stack pointer by taking the address of a local variable,
> so it is possible to write a function to check for stack overflow.

Performing such checks without getting into undefined behaviours is
tricky if not impossible, and modern compilers are quite effective at
exploiting these, rendering such checks useless.  Remember the deleted
null checks in the kernel a while back?

> We could add this in U-Boot if it is a general problem. For my
> purposes the amount of stack I intend to allocate is fairly small
> (1-2KB perhaps).

I'm sure what you _intend_ to allocate is safe, but what's to guarantee
that the values are sane?

>>>> If the size is somehow limited to a safe value, it is more efficient to
>>>> simply allocate this maximum size statically.
>>>
>>> Yes although this does waste BSS.
>>
>> Sorry, I meant a statically sized stack allocation.
>
> OK, then I suppose this is not much different from dynamic arrays?

It gives more efficient code, if nothing else.

-- 
M?ns Rullg?rd
mans at mansr.com

[U-Boot] C99 and dynamic arrays

[Måns Rullgård]

Stephen Warren <swarren@wwwdotorg.org> writes:

> On 03/13/2013 12:03 PM, M?ns Rullg?rd wrote:
>> Simon Glass <sjg@google.com> writes:
>> 
>>> Hi Mans,
>>>
>>> On Wed, Mar 13, 2013 at 3:29 AM, M?ns Rullg?rd <mans@mansr.com> wrote:
>>>> Tom Rini <tom.rini@gmail.com> writes:
>>>>
>>>>> On Tue, Mar 12, 2013 at 7:22 PM, Simon Glass <sjg@google.com> wrote:
>>>>>> Hi,
>>>>>>
>>>>>> Given that we seem to allow C99 features in U-Boot I wonder if it
>>>>>> would be OK to use dynamic arrays in SPL?
>>>>>>
>>>>>> I am trying to replace:
>>>>>>
>>>>>> ptr = malloc(size);
>>>>>>
>>>>>> with:
>>>>>>
>>>>>> char ptr[size];
>>>>>>
>>>>>> to avoid use of malloc in SPL. Can I assume that is permitted?
>>>>>
>>>>> Without knowing the underlying mechanics of how that works, "maybe".
>>>>
>>>> How it works depends on the compiler.  Some compilers implement it by
>>>> calling malloc().  GCC uses the stack.
>>>>
>>>> Regardless of how they are implemented, variable-length arrays should,
>>>> in my opinion, never be used.  There is simply no way they can be used
>>>> safely since no mechanism for detecting failure is provided.  If the
>>>> requested size is too large, you will silently overflow the stack or end
>>>> up with an invalid/null pointer.  In an environment without full memory
>>>> protection, errors resulting from this are very hard to track down.
>>>
>>> I suppose we could check the available stack space. However I don't
>>> really see a clear stack bottom in U-Boot - I think it is set up to
>>> grow downwards as much as needed. I can certainly add sanity checks on
>>> the input values.
>> 
>> There is no way to check stack usage from C.
>> 
>>>> If the size is somehow limited to a safe value, it is more efficient to
>>>> simply allocate this maximum size statically.
>>>
>>> Yes although this does waste BSS.
>> 
>> Sorry, I meant a statically sized stack allocation.
>
> But, there's also no way to detect failure in that case either.

No, but there is an obvious upper bound to the frame size.  Absent
recursion, a static analysis tool can find the maximum stack space
required starting from a given point, but only if each function uses
a fixed amount.

-- 
M?ns Rullg?rd
mans at mansr.com

[U-Boot] C99 and dynamic arrays

[Steve Strobel]

On Wed, Mar 13, 2013 at 1:55 PM, M?ns Rullg?rd <mans@mansr.com> wrote:

> >>> I suppose we could check the available stack space.
> >> There is no way to check stack usage from C.
> > Well there is an architecture-specific way. A function can generally
> > find its own stack pointer by taking the address of a local variable,
> > so it is possible to write a function to check for stack overflow.
>
> Performing such checks without getting into undefined behaviours is
> tricky if not impossible, and modern compilers are quite effective at
> exploiting these, rendering such checks useless.  Remember the deleted
> null checks in the kernel a while back?
>

If possible, it is much nicer to use a compiler option rather than
something in the application itself to check for stack overflow.  On the
Blackfin gcc there is a -mstack-check-l1 option to do this.  It has a
little overhead, but has saved my bacon.  Note that the libraries also need
to be compiled with that option if stack overflows within those libraries
are to be detected.

Steve


-- 
Steve Strobel
Link Communications, Inc.
1035 Cerise Rd
Billings, MT 59101-7378
(406) 245-5002 ext 102
(406) 245-4889 (fax)
WWW: http://www.link-comm.com
MailTo:steve.strobel at link-comm.com