Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #22800 > unrolled thread

Variable-length arrays: should they be used at all?

Back to article view | Back to comp.lang.c

Contents

  Variable-length arrays: should they be used at all? Rui Maciel <rui.maciel@gmail.com> - 2012-06-26 15:28 +0100
    Re: Variable-length arrays: should they be used at all? Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-26 11:54 -0400
    Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-06-26 21:05 +0200
      Re: Variable-length arrays: should they be used at all? Rui Maciel <rui.maciel@gmail.com> - 2012-06-26 21:04 +0100
        Re: Variable-length arrays: should they be used at all? Keith Thompson <kst-u@mib.org> - 2012-06-26 13:09 -0700
          Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-06-27 17:50 +1200
            Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-06-27 07:57 +0200
              Re: Variable-length arrays: should they be used at all? gwowen <gwowen@gmail.com> - 2012-06-27 00:49 -0700
              Re: Variable-length arrays: should they be used at all? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-06-27 13:50 +0100
                Re: Variable-length arrays: should they be used at all? Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-06-27 10:21 -0400
                  Re: Variable-length arrays: should they be used at all? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-06-27 19:56 +0100
            Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-06 00:55 +0300
              Re: Variable-length arrays: should they be used at all? Andrew Cooper <amc96@cam.ac.uk> - 2012-07-05 23:37 +0100
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-06 16:53 -0700
              Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-07-06 18:26 +1200
                Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-07 17:37 +0300
                  Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-07-08 08:03 +1200
              Re: Variable-length arrays: should they be used at all? gwowen <gwowen@gmail.com> - 2012-07-06 02:58 -0700
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-06 18:11 -0700
                  Re: Variable-length arrays: should they be used at all? gwowen <gwowen@gmail.com> - 2012-07-09 02:33 -0700
                    Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-09 11:35 -0700
                      Re: Variable-length arrays: should they be used at all? Ike Naar <ike@iceland.freeshell.org> - 2012-07-09 22:33 +0000
                        Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-10 10:52 -0700
                    Re: Variable-length arrays: should they be used at all? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-07-09 12:03 -0700
                      Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-07-10 09:19 +1200
          Re: Variable-length arrays: should they be used at all? Gareth Owen <gwowen@gmail.com> - 2012-06-27 07:25 +0100
      Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-06-27 07:10 +0200
        Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-06-27 20:48 +0200
    Re: Variable-length arrays: should they be used at all? Jens Gustedt <jens.gustedt@loria.fr> - 2012-06-26 21:13 +0200
      Re: Variable-length arrays: should they be used at all? Rui Maciel <rui.maciel@gmail.com> - 2012-06-26 20:47 +0100
        Re: Variable-length arrays: should they be used at all? Keith Thompson <kst-u@mib.org> - 2012-06-26 13:05 -0700
        Re: Variable-length arrays: should they be used at all? David Resnick <lndresnick@gmail.com> - 2012-06-26 13:51 -0700
          Re: Variable-length arrays: should they be used at all? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-06-26 17:10 -0700
          Re: Variable-length arrays: should they be used at all? Gareth Owen <gwowen@gmail.com> - 2012-06-27 07:27 +0100
          Re: Variable-length arrays: should they be used at all? Rui Maciel <rui.maciel@gmail.com> - 2012-06-27 20:23 +0100
    Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-06-27 11:20 -0700
      Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-06-28 09:35 +1200
        Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-06-27 17:23 -0700
          Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-06-28 13:06 +1200
            Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-06-29 10:48 -0700
              Re: Variable-length arrays: should they be used at all? Ian Collins <ian-news@hotmail.com> - 2012-06-30 21:58 +1200
                Re: Variable-length arrays: should they be used at all? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-06-30 03:37 -0700
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-01 19:31 -0700
              Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-06 00:54 +0300
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-06 17:58 -0700
          Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-06 00:49 +0300
            Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-06 16:38 -0700
              Re: Variable-length arrays: should they be used at all? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-07-07 18:00 +0300
                Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-07 12:40 -0700
                  Re: Variable-length arrays: should they be used at all? pacman@kosh.dhis.org (Alan Curry) - 2012-07-08 02:54 +0000
                    Re: Variable-length arrays: should they be used at all? jacob navia <jacob@spamsink.net> - 2012-07-08 13:33 +0200
                      Re: Variable-length arrays: should they be used at all? pacman@kosh.dhis.org (Alan Curry) - 2012-07-08 22:18 +0000
                        Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-09 10:57 -0700
                          Re: Variable-length arrays: should they be used at all? pacman@kosh.dhis.org (Alan Curry) - 2012-07-09 21:38 +0000
                            Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-10 11:12 -0700
                    Re: Variable-length arrays: should they be used at all? Tim Rentsch <txr@alumni.caltech.edu> - 2012-07-08 11:28 -0700

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#23219

gwowen <gwowen@gmail.com> writes:

> On Jul 7, 2:11 am, Tim Rentsch <t...@alumni.caltech.edu> wrote:
>> gwowen <gwo...@gmail.com> writes:
>> > On Jul 5, 10:55 pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
>> > wrote:
>>
>> >> > But you can do a static analysis.
>>
>> >> Once you've solved the Halting Problem!
>>
>> > You only need solve the Halting Problem if you need to do static
>> > analysis using the same algorithm on arbitrary programs / inputs.
>> > Algorithmically determining the stack usage of a small finite number
>> > of  programs / modules with constrained inputs is very much *not* the
>> > Halting Problem.
>>
>> No program can say what others will do.  Now I won't
>> just assert that, I'll prove it to you.  We will see
>> that although you might work til you drop, no code
>> can decide which others will stop.
>
> TRUE: "no code can decide which others will stop"
> FALSE: "Given a program, it is impossible to determine whether it will
> stop"
>
> Static analysis is not the Halting Problem, because we do not require
> our methods of static analysis to work on arbitrary programs, and in
> fact, as good programmers, we structure our code not only to make
> static analysis possible  but, whenever possible, to make it
> straightforward.
>
> So the generality of the Halting Problem does not preclude the
> possibility of specific static analysis.
>
> For example, let me provide a counterexample to your assertion that
> doing static analysis requires solving the Halting Problem.
>
> This non-pathological program:
>
> int main(int,char**)
> {
>   return(0);
> }
>
> terminates.
>
> I don't need to solve the Halting Problem to determine *that*
> *specific* case, and no construction of pathological counter-examples,
> which prove the impossibility of deciding the Halting Problem *in
> general* say anything about *specific* programs.
>
> inline int mysum(x,n)
> {
>    if(n==0) return(x);
>    return mysum(x+n,n-1);
> }
>
> int main()
> {
>     printf("%d\n",mysum(0,10));
> }
>
> We know how deep that program will recurse. If we know the stack
> limits, we know whether it will overflow. A suitably excitable
> compiler could even unroll the loop and statically calculate the
> answer at compile time.
>
> The general uncomputability of the Halting Problem does not preclude
> specific static analysis.

Certainly it is true that, given a finite set S of programs,
there exists a program P that can decide whether program s
will terminate, for all programs s in S.  (I'm talking here
about the question of running s starting on a blank tape,
ie, with no input, but the same result holds if an input,
or a finite set of inputs, is specified in each case (and
program inputs are always finite).)

However, saying that P exists and saying that we know how
to write program P are two very different things.  For
example, consider the set S consisting of one program
(written here in a C-ish pseudocode)

   n = 6;
   do {
      n = n + 2;
   } while(  there are two primes that add up to (n)  );

   print "A counterexample for Golbach's conjecture is", n;

Here the variables and the arithmetic is understood to encompass
integers that can be as large as needed.  Note also that it's
easy to write the test that controls the loop exit in a way that
obviously terminates.  The only question is, is there an even n
(greater than six) for which n is not the sum of two primes?
No one knows the answer to this question.  So, at least for the
present, no one knows how to write the program P that decides
(in finite time) whether the above program will terminate.

In a technical sense what you say is right:  if the set of
programs under consideration is known in advance and finite, that
is not the same as the Halting Problem, and is theoretically
decidable.  However, that statement doesn't provide any guidance
as to how we might try to write a static analysis program that
would actually work, or even a guarantee that we will be able to
find one in a finite time -- as opposed to just knowing that one
exists even though we have no idea what it is or how to find it.
The theoretical result is no help to the practical result being
sought.

[toc] | [prev] | [next] | [standalone]

#23223

On 2012-07-09, Tim Rentsch <txr@alumni.caltech.edu> wrote:
> Certainly it is true that, given a finite set S of programs,
> there exists a program P that can decide whether program s
> will terminate, for all programs s in S.  (I'm talking here
> about the question of running s starting on a blank tape,
> ie, with no input, but the same result holds if an input,
> or a finite set of inputs, is specified in each case (and
> program inputs are always finite).)

Does the set of "easy" programs need to be finite?
For instance, the set of straight-line programs
(without gotos, loops or function calls) is infinite.
It wouldn't be too hard to write an algorithm that decides
whether its input is a (goto/loop/call)-free program.

[toc] | [prev] | [next] | [standalone]

#23227

Ike Naar <ike@iceland.freeshell.org> writes:

> On 2012-07-09, Tim Rentsch <txr@alumni.caltech.edu> wrote:
>> Certainly it is true that, given a finite set S of programs,
>> there exists a program P that can decide whether program s
>> will terminate, for all programs s in S.  (I'm talking here
>> about the question of running s starting on a blank tape,
>> ie, with no input, but the same result holds if an input,
>> or a finite set of inputs, is specified in each case (and
>> program inputs are always finite).)
>
> Does the set of "easy" programs need to be finite?
> For instance, the set of straight-line programs
> (without gotos, loops or function calls) is infinite.
> It wouldn't be too hard to write an algorithm that decides
> whether its input is a (goto/loop/call)-free program.

For sure there are infinite sets of programs that can
all be analyzed.  My statement about finite sets is
more broad in that it applies to ALL finite sets,
whether the programs in them are "easy" or not.
Every program (when started on a blank tape) either
terminates or it doesn't.  So, for any given set
of programs (the set being known ahead of time), there
certainly is a program that can answer which ones
terminate, just by doing what is effectively a table
lookup.  At some level the question is only interesting
when infinite sets of programs are considered;  in that
case it matters which infinite set is being considered.

[toc] | [prev] | [next] | [standalone]

#23220

בתאריך יום שני, 9 ביולי 2012 10:33:34 UTC+1, מאת gwowen:
> 
> TRUE: "no code can decide which others will stop"
> FALSE: "Given a program, it is impossible to determine whether it will
> stop"
> 
> Static analysis is not the Halting Problem, because we do not require
> our methods of static analysis to work on arbitrary programs, and in
> fact, as good programmers, we structure our code not only to make
> static analysis possible  but, whenever possible, to make it
> straightforward.
> 
Most C programs will fall into one fo three categories. The first has a call tree without recursion. The maximum depth of the tack is given by finding th emaximum depth of the clal tree. Note this isn't mathematically correct, because there might be subroutines which are in fact unreachable. But that's not a real issue.
The second has a call tree with recursion, with the depth of the recrusion determined by the input data. So it's impossible to give a maximum limit for stack usage.
The third category has recursion with the depth limited algorithmically. If it's limited by a simple "depth" paramter, this might be soluble. But more typcial are functions like qsort(), where the depth of the recursion is limited by the size of the array it sorts, but in a way that's difficult to determine from examining the code. As a library function, qsort() itself can be coded for as a special case. There; ylou might have to give up.

[toc] | [prev] | [next] | [standalone]

#23221

On 07/10/12 07:03 AM, Malcolm McLean wrote:
> בתאריך יום שני, 9 ביולי 2012 10:33:34 UTC+1, מאת gwowen:
>>
>> TRUE: "no code can decide which others will stop"
>> FALSE: "Given a program, it is impossible to determine whether it will
>> stop"
>>
>> Static analysis is not the Halting Problem, because we do not require
>> our methods of static analysis to work on arbitrary programs, and in
>> fact, as good programmers, we structure our code not only to make
>> static analysis possible  but, whenever possible, to make it
>> straightforward.

** Please wrap your lines!! **

> Most C programs will fall into one fo three categories.

<snip stuff that reaches the far wall>

There is a forth fairly common (probably more common than recursion) 
category: programmes that avoid recursion but use function pointers. 
These increase the difficulty of a static analysis from tricky to nigh 
on impossible.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#22848

Keith Thompson <kst-u@mib.org> writes:

> But the same applies to old-style constant-size arrays.  If you declare
>
>     double mat[100][100];
>
> either at block scope 

I think at block scope most people would consider that a pretty bad
idea, for exactly the same reason.  But at least you have the potential
to do static analysis to check the necessary stack size.

> or at file scope, 

At file scope, one would certainly hope that this would cause the
program would crash *at startup*.  (I appreciate this isn't guaranteed),
and, again, static analysis would tell you the minimum RAM required.  In
the embedded case, any decent compiler will tell you whether your static
data is going to eat all your RAM.

Both of which are arguably better than UB based on input size.

[toc] | [prev] | [next] | [standalone]

#22844

Le 26/06/12 21:18, Stefan Ram a écrit :
> jacob navia <jacob@spamsink.net> writes:
>> char buffer[iList.GetSize(NULL)];
>> List *L = (List *)&buffer[0];
>> iList.InitList(L);
>
>    You can get the same with
>
> ListBuffer buffer;
> List * L =( List * )&buffer;
> iList.InitList( L );
>

Sorry but I do not understand that: what would be "ListBuffer"?

A predefined type of buffer long enough to hold a list header
structure?

If that is the case then its length MUST be known to the compiler, and
that means that the definition of the list header structure must be
disclosed, what we want to avoid precisely.

[toc] | [prev] | [next] | [standalone]

#22883

Le 27/06/12 18:36, Stefan Ram a écrit :
>
>    Ok, I see. LIST_SIZE must be either »sizeof List« or a
>    programmer-written literal, such as »104«, which is
>    error-prone.
>
>    (One could generate a header file »#define LIST_SIZE 104«
>    during the make process using means beyond the C language
>    only.)
>
>    However, in your code, you have:
>
> List *L = (List *)&buffer[0];
>
>    . Doesn't this also mean that »List« must be disclosed to
>    the client, which, as I understand it, is the actual list
>    header structure?
>

No, the actual "List" structure mustn't be disclosed at all since you
always work with POINTERS to that incomplete type and never with
the type itself.

This is the beauty of C "private" types: they are REALLY private
and you have absolutely NO CLUE at all what they actually are.

Interface and implementation are then completely separated. I can
(and have) changed the list structure several times without ever
needing to change client code.

More: Old code that was compiled long ago when the list structure
was different will STILL WORK.

[toc] | [prev] | [next] | [standalone]

#22819

Am 26.06.2012 16:28, schrieb Rui Maciel:
> In the thread "Learning C as an existing programmer", an interesting 
> discussion arose over the use of variable-length arrays (VLAs), specifically 
> the dangers they pose by not providing a way to detect potential memory 
> allocation bugs. 
> 
> GCC's page on variable-length arrays says nothing about what to expect when 
> a VLA is too large to handle.[1]  In addition, what has been said in GCC's 
> mailing list about avoiding segfaults induced by huge VLAs isn't very 
> reassuring.[2]
> 
> With this in mind, and considering that VLAs were made optional in C11, is 
> it a good idea to simply refuse using them?

- Pointers to VLA are very convenient when you have to deal with
multi-dimensional arrays
- VLA types themselves greatly improve readability of malloc calls
- VLA are really great help for function calls

double (*A)[n] = malloc(sizeof(double[n][n]));

void init(size_t n, double A[n][n]) {
   for (size_t i = 0; i < n; ++i)
     for (size_t j = 0; j < n; ++j)
          A[i][j] = 0.0;

}

Jens

[toc] | [prev] | [next] | [standalone]

#22823

Jens Gustedt wrote:

> - Pointers to VLA are very convenient when you have to deal with
> multi-dimensional arrays
> - VLA types themselves greatly improve readability of malloc calls
> - VLA are really great help for function calls
> 
> double (*A)[n] = malloc(sizeof(double[n][n]));
> 
> void init(size_t n, double A[n][n]) {
> for (size_t i = 0; i < n; ++i)
> for (size_t j = 0; j < n; ++j)
> A[i][j] = 0.0;
> 
> }

Undoubtedly, VLAs are convenient.  Yet, with that convenience comes the 
danger of making an otherwise flawless program susceptible to nasty memory 
allocation problems.  No matter how convenient VLAs might be, having to 
handle unexplainable segfaults that can't be avoided with the dilligent use 
of safeguards may not be an acceptable tradeoff.


Rui Maciel

[toc] | [prev] | [next] | [standalone]

#22825

Rui Maciel <rui.maciel@gmail.com> writes:
> Jens Gustedt wrote:
>> - Pointers to VLA are very convenient when you have to deal with
>> multi-dimensional arrays
>> - VLA types themselves greatly improve readability of malloc calls
>> - VLA are really great help for function calls
>> 
>> double (*A)[n] = malloc(sizeof(double[n][n]));
>> 
>> void init(size_t n, double A[n][n]) {
>> for (size_t i = 0; i < n; ++i)
>> for (size_t j = 0; j < n; ++j)
>> A[i][j] = 0.0;
>> 
>> }
>
> Undoubtedly, VLAs are convenient.  Yet, with that convenience comes the 
> danger of making an otherwise flawless program susceptible to nasty memory 
> allocation problems.  No matter how convenient VLAs might be, having to 
> handle unexplainable segfaults that can't be avoided with the dilligent use 
> of safeguards may not be an acceptable tradeoff.

Except that the code you quoted isn't subject to unexplainable
segfaults.  It uses a VLA type, but there are no VLA objects with
automatic storage duration; A is allocated with malloc(), which returns
NULL on failure.

The use of a VLA type makes indexing more convenient.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#22830

On Tuesday, June 26, 2012 3:47:08 PM UTC-4, Rui Maciel wrote:
> Undoubtedly, VLAs are convenient.  Yet, with that convenience comes the 
> danger of making an otherwise flawless program susceptible to nasty memory 
> allocation problems.  No matter how convenient VLAs might be, having to 
> handle unexplainable segfaults that can't be avoided with the dilligent use 
> of safeguards may not be an acceptable tradeoff.

Yep, they should be used with caution.  Mind you, the same arguments apply to using recursion. How deeply you can safely recurse, and the consequences if you go too deep, also murky.  Had a recursion related crash where somebody markedly increased the size of an automatic buffer in moderately deeply recursive code.

[toc] | [prev] | [next] | [standalone]

#22840

בתאריך יום שלישי, 26 ביוני 2012 21:51:12 UTC+1, מאת David Resnick:
> 
> Yep, they should be used with caution.  Mind you, the same arguments apply to using recursion. How deeply you can safely recurse, and the consequences if you go too deep, also murky.  Had a recursion related crash where somebody markedly increased the size of an automatic buffer in moderately deeply recursive code.
>
The difference is that recursion is usually logarithmic in depth. A malicious or careless user has to construct a degenerate tree. That's a lot harder than simply declaring that a company has 4 billion employees. 

[toc] | [prev] | [next] | [standalone]

#22850

David Resnick <lndresnick@gmail.com> writes:

> On Tuesday, June 26, 2012 3:47:08 PM UTC-4, Rui Maciel wrote:
>> Undoubtedly, VLAs are convenient.  Yet, with that convenience comes the 
>> danger of making an otherwise flawless program susceptible to nasty memory 
>> allocation problems.  No matter how convenient VLAs might be, having to 
>> handle unexplainable segfaults that can't be avoided with the dilligent use 
>> of safeguards may not be an acceptable tradeoff.
>
> Yep, they should be used with caution.  Mind you, the same arguments
> apply to using recursion. How deeply you can safely recurse, and the
> consequences if you go too deep, also murky.  

I completely agree.  But it strikes me that programmers are more aware
of the dangers of recursion than of VLAs.

[toc] | [prev] | [next] | [standalone]

#22891

David Resnick wrote:

> Yep, they should be used with caution.  Mind you, the same arguments apply
> to using recursion. 

And it is applied.  It is a common rule of thumb that recursion should 
simply be avoided in order to avoid nasty surprises, such as the ones you've 
described.


> How deeply you can safely recurse, and the
> consequences if you go too deep, also murky.  

That's essentially the problem with VLAs; if it isn't possible to know 
beforehand if a VLA will work as expected or if it will actually crash the 
program, shouldn't VLAs simply be avoided?  

Considering that there are other ways to reserve memory that at least make 
it possible to put in place the necessary safety checks to avoid having the 
program blow up in the programmer's face, using VLAs may be a risk which 
isn't worth taking.


Rui Maciel

[toc] | [prev] | [next] | [standalone]

#22881

Rui Maciel <rui.maciel@gmail.com> writes:

> In the thread "Learning C as an existing programmer", an interesting 
> discussion arose over the use of variable-length arrays (VLAs), specifically 
> the dangers they pose by not providing a way to detect potential memory 
> allocation bugs. 
>
> GCC's page on variable-length arrays says nothing about what to expect when 
> a VLA is too large to handle.[1]  In addition, what has been said in GCC's 
> mailing list about avoiding segfaults induced by huge VLAs isn't very 
> reassuring.[2]
>
> With this in mind, and considering that VLAs were made optional in C11, is 
> it a good idea to simply refuse using them?

There are two distinct concerns here.  Let's take them one at a
time.

First, encountering a VLA declaration during execution may blow
the stack and crash, and there is no portable way to detect or
deal with that.  However, it is easy for implementations to
provide a way of doing that, without adding any new language
constructs, as I explained in another posting.

Second, VLAs have not been implmented by some vendors (a certain
laggard major software company comes to mind here), and VLA
support is optional in C11, presumably so those vendors can claim
full C11 compliance without having to provide VLA support.

The flip side to the second concern is that many or most major
implementations (at least hosted implementations) do provide VLA
support, and will continue to do so under C11, despite its being
optional.  The laggards will keep being laggards, whether VLA
support is optional or not, because they think their user base
doesn't care about it (or perhaps because they think their user
base has to accept what they do whether the user base cares about
it or not).

The flip side of the first concern is that, one, it often isn't a
big deal in practice;  two, implementors should be encouraged to
supply a mechanism for detecting/handling VLA allocation failure,
since it is easy to provide such a mechanism;  and three, VLA
support provides an important benefit that does not have the
associated risk of undetectable allocation failure, namely,
variably modified types and more specifically pointers to VLAs,
which are useful even if VLA objects are never declared.

Personally, I find VLA support useful and convenient, whether
using VLAs themselves or just pointers to them, and in a wider
variety of circumstances than I originally expected.  Vendors
and implementors will provide VLA support if developers use
them, and very likely won't if they don't.  So my conclusion
is somewhat the opposite of yours -- developers *should* use
VLAs and variably modified types whenever they are useful and
convenient to express the programming task at hand, and also
should encourage and prevail upon vendors and implementors to
supply better VLA support, such as a mechanism for detecting
and handling allocation failure like the one described in
another thread.  VLA support is both convenient and useful;
if demand for it is high enough, implementations that provide
VLAs will become both better and more ubiquitous.

[toc] | [prev] | [next] | [standalone]

#22899

On 06/28/12 06:20 AM, Tim Rentsch wrote:
>
> There are two distinct concerns here.  Let's take them one at a
> time.
>
> First, encountering a VLA declaration during execution may blow
> the stack and crash, and there is no portable way to detect or
> deal with that.  However, it is easy for implementations to
> provide a way of doing that, without adding any new language
> constructs, as I explained in another posting.

<snip second>

> The flip side of the first concern is that, one, it often isn't a
> big deal in practice;  two, implementors should be encouraged to
> supply a mechanism for detecting/handling VLA allocation failure,
> since it is easy to provide such a mechanism;  and three, VLA
> support provides an important benefit that does not have the
> associated risk of undetectable allocation failure, namely,
> variably modified types and more specifically pointers to VLAs,
> which are useful even if VLA objects are never declared.

While the "easy to provide" may be true on some platforms, it will be 
false for others without memory management.  Even the easy 
implementations may come at a run time cost which negates the 
performance advantages of VLAs over dynamically allocated memory.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#22910

Ian Collins <ian-news@hotmail.com> writes:

> On 06/28/12 06:20 AM, Tim Rentsch wrote:
>>
>> There are two distinct concerns here.  Let's take them one at a
>> time.
>>
>> First, encountering a VLA declaration during execution may blow
>> the stack and crash, and there is no portable way to detect or
>> deal with that.  However, it is easy for implementations to
>> provide a way of doing that, without adding any new language
>> constructs, as I explained in another posting.
>
> <snip second>
>
>> The flip side of the first concern is that, one, it often isn't a
>> big deal in practice;  two, implementors should be encouraged to
>> supply a mechanism for detecting/handling VLA allocation failure,
>> since it is easy to provide such a mechanism;  and three, VLA
>> support provides an important benefit that does not have the
>> associated risk of undetectable allocation failure, namely,
>> variably modified types and more specifically pointers to VLAs,
>> which are useful even if VLA objects are never declared.
>
> While the "easy to provide" may be true on some platforms, it will be
> false for others without memory management.  Even the easy
> implementations may come at a run time cost which negates the
> performance advantages of VLAs over dynamically allocated memory.

I guess you missed the posting where I explained this.  No
elaborate memory management (eg, malloc() etc) is needed --
just ordinary stack allocation, the way VLAs are usually
done.  For example:

    int
    function_needing_a_VLA( int n ){
        ...
        double values[n][n];
        if(  ! &values  ){
            ... here we have detected an allocation failure,
                and the stack is not blown (although of course
                we cannot use the 'values' VLA), so the error
                condition can be handled appropriately (eg,
                returning an error flag, longjmp(), ...)  ...
        } else {
            ... here we can use the 'values' VLA safely ...
        }
    }

How would this be done?  Simple.  The compiler notices the check
of the address of the VLA immediately after its declaration,
and does that check _before_ adjusting the stack pointer, ie,
generated code would include an addition (to the current stack
pointer) and a compare (to a stack limit value), before installing
the new value as the current stack pointer.  It's hard to imagine
an architecture where VLAs can be implemented cheaply but this
check is expensive to do;  so the runtime cost is pretty close to
zero, and actually would be zero for code that uses VLAs without
any checking.

Incidentally, here I have written the "VLA-using code" as a
separate branch of the if() statement, but there is no reason
that would have to be required.  I wrote it this way just to
emphasize the different possible execution paths.

Does that seem a little better now?

[toc] | [prev] | [next] | [standalone]

#22912

On 06/28/12 12:23 PM, Tim Rentsch wrote:
> Ian Collins<ian-news@hotmail.com>  writes:
>
>> On 06/28/12 06:20 AM, Tim Rentsch wrote:
>>>
>>> There are two distinct concerns here.  Let's take them one at a
>>> time.
>>>
>>> First, encountering a VLA declaration during execution may blow
>>> the stack and crash, and there is no portable way to detect or
>>> deal with that.  However, it is easy for implementations to
>>> provide a way of doing that, without adding any new language
>>> constructs, as I explained in another posting.
>>
>> <snip second>
>>
>>> The flip side of the first concern is that, one, it often isn't a
>>> big deal in practice;  two, implementors should be encouraged to
>>> supply a mechanism for detecting/handling VLA allocation failure,
>>> since it is easy to provide such a mechanism;  and three, VLA
>>> support provides an important benefit that does not have the
>>> associated risk of undetectable allocation failure, namely,
>>> variably modified types and more specifically pointers to VLAs,
>>> which are useful even if VLA objects are never declared.
>>
>> While the "easy to provide" may be true on some platforms, it will be
>> false for others without memory management.  Even the easy
>> implementations may come at a run time cost which negates the
>> performance advantages of VLAs over dynamically allocated memory.
>
> I guess you missed the posting where I explained this.  No
> elaborate memory management (eg, malloc() etc) is needed --
> just ordinary stack allocation, the way VLAs are usually
> done.  For example:
>
>      int
>      function_needing_a_VLA( int n ){
>          ...
>          double values[n][n];
>          if(  !&values  ){
>              ... here we have detected an allocation failure,
>                  and the stack is not blown (although of course
>                  we cannot use the 'values' VLA), so the error
>                  condition can be handled appropriately (eg,
>                  returning an error flag, longjmp(), ...)  ...
>          } else {
>              ... here we can use the 'values' VLA safely ...
>          }
>      }
>
> How would this be done?  Simple.  The compiler notices the check
> of the address of the VLA immediately after its declaration,
> and does that check _before_ adjusting the stack pointer, ie,
> generated code would include an addition (to the current stack
> pointer) and a compare (to a stack limit value), before installing
> the new value as the current stack pointer.

Assuming you have a stack limit value available.

> It's hard to imagine
> an architecture where VLAs can be implemented cheaply but this
> check is expensive to do;  so the runtime cost is pretty close to
> zero, and actually would be zero for code that uses VLAs without
> any checking.

I would expect it to be expensive on most, unless they already have a 
mechanism in place.

> Incidentally, here I have written the "VLA-using code" as a
> separate branch of the if() statement, but there is no reason
> that would have to be required.  I wrote it this way just to
> emphasize the different possible execution paths.
>
> Does that seem a little better now?

Not really, I'd be interesting in knowing about real implementations 
that have a trivial means of determining how far through the stack you are.

Even where you can check, there's always the pathological case of the 
VLA consuming almost all of the stack and the next function call failing!

I guess working an a field where resources are constrained and static 
analysis is frequently used to determine stack limits, I'm somewhat biased.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#22989

Ian Collins <ian-news@hotmail.com> writes:

> On 06/28/12 12:23 PM, Tim Rentsch wrote:
>> Ian Collins<ian-news@hotmail.com>  writes:
>>
>>> On 06/28/12 06:20 AM, Tim Rentsch wrote:
>>>>
>>>> There are two distinct concerns here.  Let's take them one at a
>>>> time.
>>>>
>>>> First, encountering a VLA declaration during execution may blow
>>>> the stack and crash, and there is no portable way to detect or
>>>> deal with that.  However, it is easy for implementations to
>>>> provide a way of doing that, without adding any new language
>>>> constructs, as I explained in another posting.
>>>
>>> <snip second>
>>>
>>>> The flip side of the first concern is that, one, it often isn't a
>>>> big deal in practice;  two, implementors should be encouraged to
>>>> supply a mechanism for detecting/handling VLA allocation failure,
>>>> since it is easy to provide such a mechanism;  and three, VLA
>>>> support provides an important benefit that does not have the
>>>> associated risk of undetectable allocation failure, namely,
>>>> variably modified types and more specifically pointers to VLAs,
>>>> which are useful even if VLA objects are never declared.
>>>
>>> While the "easy to provide" may be true on some platforms, it will be
>>> false for others without memory management.  Even the easy
>>> implementations may come at a run time cost which negates the
>>> performance advantages of VLAs over dynamically allocated memory.
>>
>> I guess you missed the posting where I explained this.  No
>> elaborate memory management (eg, malloc() etc) is needed --
>> just ordinary stack allocation, the way VLAs are usually
>> done.  For example:
>>
>>      int
>>      function_needing_a_VLA( int n ){
>>          ...
>>          double values[n][n];
>>          if(  !&values  ){
>>              ... here we have detected an allocation failure,
>>                  and the stack is not blown (although of course
>>                  we cannot use the 'values' VLA), so the error
>>                  condition can be handled appropriately (eg,
>>                  returning an error flag, longjmp(), ...)  ...
>>          } else {
>>              ... here we can use the 'values' VLA safely ...
>>          }
>>      }
>>
>> How would this be done?  Simple.  The compiler notices the check
>> of the address of the VLA immediately after its declaration,
>> and does that check _before_ adjusting the stack pointer, ie,
>> generated code would include an addition (to the current stack
>> pointer) and a compare (to a stack limit value), before installing
>> the new value as the current stack pointer.
>
> Assuming you have a stack limit value available.

I find it hard to believe that there's a platform in use today
where some limit value (perhaps a conservative one) could not be
discovered.  However, assuming there is such a platform, there's
an easy way out - it can just always indicate that an allocation
fails.  The absence of a safely allocated VLA will be detected
and handled as the program sees fit.

>> It's hard to imagine
>> an architecture where VLAs can be implemented cheaply but this
>> check is expensive to do;  so the runtime cost is pretty close to
>> zero, and actually would be zero for code that uses VLAs without
>> any checking.
>
> I would expect it to be expensive on most, unless they already
> have a mechanism in place.

I have no idea why you think that.  All that is needed is
(1) getting the address of the place in the stack where
the VLA would go, (2) an addition (or subtraction) to
compare against a stack limit, and (3) the availability of
a stack limit to compare against.  Parts (1) and (2) are
pretty much necessary for (inexpensive) VLAs without checking;
part (3) was covered above.  It's a few instructions, I would
guess, and not more than that, on most platforms out there.

So let me turn that around and ask if you can give an
example of a platform where it's easy to provide VLAs
but hard to provide checking of the kind I've described.

>> Incidentally, here I have written the "VLA-using code" as a
>> separate branch of the if() statement, but there is no reason
>> that would have to be required.  I wrote it this way just to
>> emphasize the different possible execution paths.
>>
>> Does that seem a little better now?
>
> Not really, I'd be interesting in knowing about real implementations
> that have a trivial means of determining how far through the stack you
> are.

Stack pointer is an address?  Easy to find that address (at least
approximately)?  There is a static limit (or a current limit that
can be easily computed)?  For me it's hard to imagine an actual
environment (as opposed to a hypothetical one) where it would be
expensive.

> Even where you can check, there's always the pathological case of the
> VLA consuming almost all of the stack and the next function call
> failing!

Presumably VLAs (at least "large" ones) would be used primarily
in leaf procedures, but even if they aren't, there is a way to
protect against such eventualities:

    { char test_space[ n*n* sizeof (double) + SPACE_FOR_REMAINING_CALLS ];
      if(  ! &test_space  ){
        // OOPS! aren't going to have enough..  handle that
        // eg, return or longjmp()
      }
    }
    double values[n][n];
    // okay to proceed here since the earlier check worked

> I guess working an a field where resources are constrained and static
> analysis is frequently used to determine stack limits, I'm somewhat
> biased.

Clearly the environments I'm used to working in are different from
yours.  But I don't think what I've suggested (ie, a mechanism to
detect VLA allocation failure) is at odds with what you do.  It may
be the case that VLAs still don't work well in your environment;  if
that's how it is, well then that's how it is.  However, adding this
capability makes it more likely that VLAs _could_ be useful (perhaps
in conjunction with more elaborate static analysis) in those
environments.  Certainly I don't mean to advocate use of VLAs in
environments where they shouldn't be used.  At the same time, I
would like them to be capable of being used more safely in
environments where using VLAs is reasonable.  I think the benefit
is (relatively) large, and the cost in terms of implemention
effort is pretty small.  Of course, I'm just making semi-educated
guesses about the implementation costs, so if anyone has some
information about actual platforms or implementations that would
help nail those down it would be good to hear about that.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web