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

[Tim Rentsch]

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.

Imagine we have a procedure called P, that will snoop in
the source code of programs to see there aren't infinite
loops that go round and around; and P prints the word
"Fine" if no looping is found.

You feed in your code, and the input it needs, and then
P takes them both and it studies and reads, to compute
whether things will all end as they should (as opposed
to all loopy the way that they could).

Well, the truth is that P cannot possibly be, because
if you wrote it and gave it to me, I could use P to
set up a logical bind that would shatter your reason
and scramble your mind.

Here's the trick I would use, and it's simple to do.
I'd define a procedure -- we'll name the thing Q --
that would take any program and call P (of course) to
tell if it looped, by reading the source.

And if so, Q would simply print "Loop" and then stop;
but if no, Q would go right back up to the top, and start
off again, looping endlessly back, til the universe dies
and is frozen and black.

And this program called Q wouldn't stay on the shelf;
I would run it, and fiendishly feed it itself. What
behaviour results when I do this with Q? When it reads
its own source, just what will it do?

If P warns of loops, Q will print "Loop" and quit; yet
P is supposed to speak truly of it. So if Q's going to
quit, then P should say, "Fine" -- which will make Q go
back to its very first line.

No matter what P would have done, Q will scoop it: Q
uses P's output to make P look stupid. If P gets
things right then it lies in its tooth; and if it
speaks falsely, it's telling the truth!

I've created a paradox, neat as can be, simply by using
your putative P. When you assumed P you stepped into a
snare; this assumption has led you right into my lair.

How can we escape from this logical mess? I don't have
to tell you -- I'm sure you can guess! By reductio,
there cannot possibly be a procedure that acts like the
mythical P.

You can never discover mechanical means for predicting
the acts of computing machines. Such things simply
cannot be done, so we users must find our own bugs:
our computers are losers.





(Original written by Geoffrey K. Pullum, University of
Edinburgh. He later wrote a revised version, but I
like the original better, even though it has "bugs"
in it; the more recent version is available at:

http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html
)

 

[Phil Carmody]

On 06/27/12 08:09 AM, Keith Thompson wrote:

But the same applies to old-style constant-size arrays. If you declare

double mat[100][100];

either at block scope or at file scope, there's no mechanism to detect
an allocation failure.

But you can do a static analysis.

Once you've solved the Halting Problem!

Don't you remember the tool I wrote to analyse the base station code
way back when??

I remember the base station code halting, so presumably your code was
just "echo 1" or similar.

Phil
--

I'd argue that there is much evidence for the existence of a God.

Pics or it didn't happen.
-- Tom (/. uid 822)

 

[Phil Carmody]

For example:

int
function_needing_a_VLA( int n ){
...
double values[n][n];
if( ! &values ){
... here we have detected an allocation failure, ...
How would this be done? Simple. The compiler notices the check
of the address of the VLA immediately after its declaration

This may have been covered elsethread (I have a lot to catch up on)
but was there any reason why you chose to decorate the test with
an & operator? Why would
if(!values) {
not be an equally workable idiom? (I like the idea of there being
some idiom for this purpose, it does leave the language a bit
fragile without it.)

I think both should be workable. More specifically,
if either works I think the other should work the
same way, otherwise it violates The Law of Least
Astonishment. I chose this way of writing it so
the test sticks out like a very large sore thumb, to
make it very clear to a human reader that something
unusual is going on. But as far as the compiler
goes I think the two forms should be interchangeable.
And I'm happy to leave the question of which style
is better for another time...

*phew* - I'm glad I wasn't missing something.

I only suggested my alternative as I considered the less decorated
form to be more obvious. However, the least surprise principle does
unify the two.

The thing I like about your suggestion is that it has backward
compatibility. If the compiler does not understand the idiom, it will
just say to itself (and maybe you) "that condition's always true -
duh!" and let the code plod on regardless, as it would have done
without the check.

Do you think it's worth migrating this to c.s.c? I'm definitely pro-
it.

Phil
--

I'd argue that there is much evidence for the existence of a God.

Pics or it didn't happen.
-- Tom (/. uid 822)

 

[Tim Rentsch]

For example:

int
function_needing_a_VLA( int n ){
...
double values[n][n];
if( ! &values ){
... here we have detected an allocation failure,
...
How would this be done? Simple. The compiler notices the check
of the address of the VLA immediately after its declaration

This may have been covered elsethread (I have a lot to catch up on)
but was there any reason why you chose to decorate the test with
an & operator? Why would
if(!values) {
not be an equally workable idiom? (I like the idea of there being
some idiom for this purpose, it does leave the language a bit
fragile without it.)

I think both should be workable. More specifically,
if either works I think the other should work the
same way, otherwise it violates The Law of Least
Astonishment. I chose this way of writing it so
the test sticks out like a very large sore thumb, to
make it very clear to a human reader that something
unusual is going on. But as far as the compiler
goes I think the two forms should be interchangeable.
And I'm happy to leave the question of which style
is better for another time...

*phew* - I'm glad I wasn't missing something.

I only suggested my alternative as I considered the less
decorated form to be more obvious.

It's interesting that we had the same goal but reached
opposite conclusions about how to do so.

However, the least surprise principle does unify the two.

Yes; I find that principle one of the most important in
programming language design (and violated depressingly
often, but darned if I'm going to be the one to violate
it!).

The thing I like about your suggestion is that it has
backward compatibility. If the compiler does not
understand the idiom, it will just say to itself (and
maybe you) "that condition's always true - duh!" and let
the code plod on regardless, as it would have done without
the check.

Yes, that's definitely a point in its favor (and
intentionally so, for obvious reasons).

Do you think it's worth migrating this to c.s.c? I'm
definitely pro- it.

It's nice to find someone who appreciates it.

I'm not opposed to raising the question in c.s.c, and
in fact starting a new thread on the subject might stir
up more comments and additional interest. I'm not sure
if c.s.c is exactly the right forum (not that I know
what is), because before proposing a language feature
it would be good to get some implementation to put it
in and get some level of experience using it (not to
mention what it would take to implement it). Having
said that, I think I will try starting a c.s.c thread
pretty soon (which practically speaking probably means
tomorrow) and see what transpires.

 

[Ian Collins]

On 06/27/12 08:09 AM, Keith Thompson wrote:

But the same applies to old-style constant-size arrays. If you declare

double mat[100][100];

either at block scope or at file scope, there's no mechanism to detect
an allocation failure.

But you can do a static analysis.

Once you've solved the Halting Problem!

Don't you remember the tool I wrote to analyse the base station code
way back when??

I remember the base station code halting, so presumably your code was
just "echo 1" or similar.

 

[Alan Curry]

[about using if(&array) as a test for VLA allocation failure]

It's nice to find someone who appreciates it.

I'm not opposed to raising the question in c.s.c, and
in fact starting a new thread on the subject might stir
up more comments and additional interest. I'm not sure
if c.s.c is exactly the right forum (not that I know
what is), because before proposing a language feature
it would be good to get some implementation to put it
in and get some level of experience using it (not to
mention what it would take to implement it). Having
said that, I think I will try starting a c.s.c thread
pretty soon (which practically speaking probably means
tomorrow) and see what transpires.

As far as I know, the usual method of allocating VLAs is to just decrement
the stack pointer register have faith that the OS will make the pages appear
when they're needed.

Should physical memory to be reserved at the time of the test? Is there even
a syscall to reserve physical memory for not-yet-used stack pages on any
current OS, or will we have to invent a new mmap flag?

 

[jacob navia]

Le 08/07/12 04:54, Alan Curry a écrit :

As far as I know, the usual method of allocating VLAs is to just decrement
the stack pointer register have faith that the OS will make the pages appear
when they're needed.

You can't do that under windows

Should physical memory to be reserved at the time of the test? Is there even
a syscall to reserve physical memory for not-yet-used stack pages on any
current OS, or will we have to invent a new mmap flag?

Under windows you touch the page below the current stack pointer and the
system will retrieve you 4096 bytes extending the stack.

If you touch a byte more than a page below the current stack the
program will crash. If you want an automatic array of more than 4096
bytes (say a 64K array) you have to build a loop touching each page
in the right sequence until you reach 64K.

Apparently Linux is clever enough to avoid that.

 

[Tim Rentsch]

[about using if(&array) as a test for VLA allocation failure]

It's nice to find someone who appreciates it.

I'm not opposed to raising the question in c.s.c, and
in fact starting a new thread on the subject might stir
up more comments and additional interest. I'm not sure
if c.s.c is exactly the right forum (not that I know
what is), because before proposing a language feature
it would be good to get some implementation to put it
in and get some level of experience using it (not to
mention what it would take to implement it). Having
said that, I think I will try starting a c.s.c thread
pretty soon (which practically speaking probably means
tomorrow) and see what transpires.

As far as I know, the usual method of allocating VLAs is to just decrement
the stack pointer register have faith that the OS will make the pages appear
when they're needed.

Should physical memory to be reserved at the time of the test? Is there even
a syscall to reserve physical memory for not-yet-used stack pages on any
current OS, or will we have to invent a new mmap flag?

These are good questions. I have some ideas for preliminary
answers, but let me do a little more research before getting into
that so I'll be able to keep up with the subsequent discussion.

 

[Alan Curry]

Le 08/07/12 04:54, Alan Curry a écrit :

You can't do that under windows



Under windows you touch the page below the current stack pointer and the
system will retrieve you 4096 bytes extending the stack.

If you touch a byte more than a page below the current stack the
program will crash. If you want an automatic array of more than 4096
bytes (say a 64K array) you have to build a loop touching each page
in the right sequence until you reach 64K.

Now that you mention it, I think I have seen that loop before in some Windows
assembly dumps, inside a helper function that acts like alloca(). I suppose
the compiler puts it into the prologue of every function with more than one
page worth of autos. I assume gcc for Windows does it already, which means it
wouldn't be too much effort to also get gcc to do the same thing on other
platforms.

What is the normal reaction when that touch-every-page loop runs out of
memory? The process dies of an unhandled exception is my guess. The proposed
clean failure mode for VLAs would require a tricky handler for that
exception.

Apparently Linux is clever enough to avoid that.

Looking it up now... there is more clever stuff than I expected in the
arch-specific page fault handlers. On x86 it uses the current value of the
userspace stack pointer as a limit. On PPC it looks at whether the fault was
caused by one of the special stack-frame-setup instructions.

Aside from the arch-specific magic, the main rule is that a page fault that
occurs anywhere between the current bottom of stack and the top of the
nearest lower allocated region is a candidate for stack growth.

 

[gwowen]

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.

 

[Tim Rentsch]

Le 08/07/12 04:54, Alan Curry a @C3{A9}crit :

You can't do that under windows



Under windows you touch the page below the current stack pointer and the
system will retrieve you 4096 bytes extending the stack.

If you touch a byte more than a page below the current stack the
program will crash. If you want an automatic array of more than 4096
bytes (say a 64K array) you have to build a loop touching each page
in the right sequence until you reach 64K.

Now that you mention it, I think I have seen that loop before in some Windows
assembly dumps, inside a helper function that acts like alloca(). I suppose
the compiler puts it into the prologue of every function with more than one
page worth of autos. I assume gcc for Windows does it already, which means it
wouldn't be too much effort to also get gcc to do the same thing on other
platforms.

What is the normal reaction when that touch-every-page loop runs out of
memory? The process dies of an unhandled exception is my guess. The proposed
clean failure mode for VLAs would require a tricky handler for that
exception. [snip further unrelated]

I'm curious to know why you say the handler needed would have to
be tricky. ISTM that it would be easy to provide a handler for a
VLA allocation checker, since the allocation checker code can be
written knowing that it might get an exception, and take steps in
advance (eg, record progress information in global side channels)
that would make it easy for the handler to get things back on
track. Or are you talking about some different scheme, eg, a
generic handler with no specific knowledge of the VLA allocation
check mechanism?

 

[Malcolm McLean]

בת×ריך ×™×•× ×©× ×™,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 findingth 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. Ifit's limited by a simple "depth" paramter, this might be soluble. But moretypcial 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 canbe coded for as a special case. There; ylou might have to give up.

 

[Ian Collins]

בת×ריך ×™×•× ×©× ×™, 9 ביולי 2012 10:33:34 UTC+1, מ×ת gwowen:

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

 

[Alan Curry]

What is the normal reaction when that touch-every-page loop runs out of
memory? The process dies of an unhandled exception is my guess. The proposed
clean failure mode for VLAs would require a tricky handler for that
exception. [snip further unrelated]

I'm curious to know why you say the handler needed would have to
be tricky. ISTM that it would be easy to provide a handler for a
VLA allocation checker, since the allocation checker code can be
written knowing that it might get an exception, and take steps in
advance (eg, record progress information in global side channels)
that would make it easy for the handler to get things back on
track. Or are you talking about some different scheme, eg, a
generic handler with no specific knowledge of the VLA allocation
check mechanism?

Just a hunch. Aversion to signal handlers and non-local jumps. Anyway, a
single explicit syscall is cleaner than a loop that does nothing but
provoke a bunch of page faults, isn't it?

Plus, the syscall (new mmap flag) could respect vm_overcommit setting by
becoming a no-op when overcommit is enabled.

Also I'm not sure when you intended the allocation to occur. In this
fictional example:

foo_t *foo(char *filename, const char *default)
{
char buf[strlen(default)+1];

if(exists(filename))
return extract_some_information_from_the_file(filename);

if(&buf==0)
return NULL;

strcpy(buf, default);
return parse_default(buf); /* needs writable string. uses strtok */
}

Should the request for physical memory for buf occur during the function
prologue, even though it might not be tested?

Or should the request be made at the point of the &buf==0 comparison?
Would the answer change if the declaration of buf was moved down to just
before the &buf==0 test?

Whoever writes working code will have priority in answering these
questions

 

[Ike Naar]

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.

 

[Tim Rentsch]

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.

 

[Tim Rentsch]

What is the normal reaction when that touch-every-page loop runs out of
memory? The process dies of an unhandled exception is my guess. The proposed
clean failure mode for VLAs would require a tricky handler for that
exception. [snip further unrelated]

I'm curious to know why you say the handler needed would have to
be tricky. ISTM that it would be easy to provide a handler for a
VLA allocation checker, since the allocation checker code can be
written knowing that it might get an exception, and take steps in
advance (eg, record progress information in global side channels)
that would make it easy for the handler to get things back on
track. Or are you talking about some different scheme, eg, a
generic handler with no specific knowledge of the VLA allocation
check mechanism?

Just a hunch. Aversion to signal handlers and non-local jumps.

I hear that. I was just wondering if there was anything more
specific.

Anyway, a
single explicit syscall is cleaner than a loop that does nothing but
provoke a bunch of page faults, isn't it?

Yes, very likely so. However I think it is also important to
think about what to do when such a syscall hasn't yet been
provided.

Plus, the syscall (new mmap flag) could respect vm_overcommit setting by
becoming a no-op when overcommit is enabled.

Absolutely, better system support is always helpful.

Also I'm not sure when you intended the allocation to occur. In this
fictional example:

foo_t *foo(char *filename, const char *default)
{
char buf[strlen(default)+1];

if(exists(filename))
return extract_some_information_from_the_file(filename);

if(&buf==0)
return NULL;

strcpy(buf, default);
return parse_default(buf); /* needs writable string. uses strtok */
}

Should the request for physical memory for buf occur during the function
prologue, even though it might not be tested?

Good question. Normally I would expect the declaration for 'buf' to
be moved down after the first if(), to just above the check. However,
assuming that wasn't done and assuming this kind of deferred checking
is allowed (and certainly that's possible), I think this is a quality
of implementation question, not a language definition question. I
agree though that there are some subtle issues there that need to be
explored.

Or should the request be made at the point of the &buf==0 comparison?
Would the answer change if the declaration of buf was moved down to just
before the &buf==0 test?

In that case I think it's clear cut - both allocation and check would
be done only after the initial if() completes (or possibly earlier,
subject to the 'as if' rule).

Whoever writes working code will have priority in answering these
questions

Right. And that is essential if such a facility is ever to
be considered for inclusion in some future version of the
standard.