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 3 of 3 — ← Prev page 1 2 [3]

#23018

On 06/30/12 05:48 AM, Tim Rentsch wrote:
> Ian Collins<ian-news@hotmail.com>  writes:
>> On 06/28/12 12:23 PM, Tim Rentsch wrote:
>>>
>>> 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.

While I admit I've never looked too hard, I don't recall any of the 
embedded systems I've used having one.  It simply isn't a very common 
thing to do.

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

Well on most Unix systems the stack limit can be changed on a running 
process, so that muddies the waters a bit.  The Solaris compiler does 
have a stack check option, but I believe it causes a early SEGV rather 
than an error return.  I know Solaris also has a mechanism for getting 
the process context, which include the stack.  So yes VLAs could be 
checked, but the compiler and the OS would have to cooperate.

Having to make a function call behind the scenes removes the simplicity 
and immediacy of VLAs.  Does it narrow the performance gap with malloc 
significantly?  Maybe.

Maybe a compromise would be to standardise a function like alloca with a 
requirement to perform a space check?

-- 
Ian Collins

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

#23020

בתאריך יום שבת, 30 ביוני 2012 10:58:52 UTC+1, מאת Ian Collins:
> On 06/30/12 05:48 AM, Tim Rentsch wrote:
>
> Maybe a compromise would be to standardise a function like alloca with a 
> requirement to perform a space check?
> 
It doesn't need a requirement to perform a space check. it just needs to be allowed to do so.
The thinking is that if the program has to respond gracefully to out of memory conditions, the platform will provide some way of doing the check. You might need to set a compiler option that entails that alloca() goes slower. But on many platforms there's nothing you can do on out of memory. I believe that Linux automatically kills a process at random if system memory is exhausted. So on this system it's pretty pointless to do anything other than segfault, and there's no real reason to slow down alloca().

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

#23065

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

> On 06/30/12 05:48 AM, Tim Rentsch wrote:
>> Ian Collins<ian-news@hotmail.com>  writes:
>>> On 06/28/12 12:23 PM, Tim Rentsch wrote:
>>>>
>>>> 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.
>
> While I admit I've never looked too hard, I don't recall any of the
> embedded systems I've used having one.  It simply isn't a very common
> thing to do.

Perhaps they don't at present, but is it hard for them to do so?
If what's needed is easy and cheap to provide, I expect those
OS's (or whatever is the moral equivalent) that don't already
provide that would likely be upgraded to do so.  Also, even if
there is no OS support to find a dynamic stack limit, the
implementation can self-impose a static limit (which could be
checked once at program startup if nothing else), and then
check VLA allocation against the static limit.

>>>> 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.
>
> Well on most Unix systems the stack limit can be changed on a running
> process, so that muddies the waters a bit.

In Linux at least, setrlimit() is defined in libc.a.  No reason
it couldn't be changed to remember the current stack limit in
a global variable.

(I assume you're talking about a process changing its own
stack limit, not having it changed by a different process,
unbeknownst to the affected process.  Obviously there is
no way to protect against arbitrary outside interference,
but that's true of all sorts of things, not just this.)

> The Solaris compiler does
> have a stack check option, but I believe it causes a early SEGV rather
> than an error return.

No reason an implementation couldn't have its own signal handler
installed to get that signal, and handle it appropriately
(including re-dispatching a SEGV that arises not as a result of
VLA stack adjustment, if such is needed).  The signal() function
is part of the standard C library.

> I know Solaris also has a mechanism for getting
> the process context, which include the stack.  So yes VLAs could be
> checked, but the compiler and the OS would have to cooperate.

Certainly I expect there would be some level of cooperation
between the OS and the implementation (or maybe I should
say that as there would be some level of cooperation from
the OS).  However I don't think the amount of cooperation
needed is very large - it could be as simple as memory
location with a pre-defined name that stores the current
stack limit.  As long as there is _some_ cooperative
mechanism, it doesn't have to be the _same_ mechanism from
platform to platform:  the implementation would know
which mechanism to use for the different platforms it
supported.

> Having to make a function call behind the scenes removes the
> simplicity and immediacy of VLAs.  Does it narrow the performance gap
> with malloc significantly?  Maybe.

Perhaps I am wrong in this, but I believe (or assume) that in
most cases a fairly good estimate (ie, a safe estimate, but not
wildly wrong) can be made without a function call being
necessary.  However, even if a function call is needed, if it's a
user-space function call (so no kernel context switch is needed),
I would expect the performance to be better than malloc(), both
because the deallocation code is simpler, and because in many or
most cases no explicit deallocation cycles are needed -- it just
happens automatically when the stack-unwinding procedure return
is done.

> Maybe a compromise would be to standardise a function like alloca with
> a requirement to perform a space check?

In a sense that is what I'm proposing, although with more
integrated semantics than alloca().  A key difference between
alloca() and VLAs is, once you do an alloca(), that space is used
(ie, never deallocated) until the function exits.  By attaching
the checking semantics to VLAs, space can be allocated on the
stack (perhaps with a function call overhead), but deallocation
occurs (by decrementing the stack pointer, presumably) at the end
of the compound statement the VLA is in, which could be long
before the function exit point.

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

#23095

Tim Rentsch <txr@alumni.caltech.edu> writes:
[SNIP = notionally agree]
> Presumably VLAs (at least "large" ones) would be used primarily
> in leaf procedures.
 
I wouldn't expect that at all. If it's big, it will be allocated 
once early on and then acted upon many times, in my experience.
(And possibly by functions of unknown complexity and depth - say
you're creating a bitmap on the stack, and then running arbitrary
filters across that image - how much stack space does an arbitrary
filter take?)

Phil
-- 
> I'd argue that there is much evidence for the existence of a God.
Pics or it didn't happen.
-- Tom (/. uid 822)

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

#23126

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

> Tim Rentsch <txr@alumni.caltech.edu> writes:
> [SNIP = notionally agree]
>> Presumably VLAs (at least "large" ones) would be used primarily
>> in leaf procedures.
>  
> I wouldn't expect that at all. If it's big, it will be allocated 
> once early on and then acted upon many times, in my experience.
> (And possibly by functions of unknown complexity and depth - say
> you're creating a bitmap on the stack, and then running arbitrary
> filters across that image - how much stack space does an arbitrary
> filter take?)

In that case it's safe to say that our expectations are
different.

I might modify my previous statement to say "leaf or near-leaf
procedures", meaning functions that have a relatively fixed,
well-defined, and fairly shallow forest of called procedures,
probably done as an aid to program structuring.

My sense though is that you mean greater variability than that,
perhaps even unknown at compile time and potentially of unknown
(and large?) depth.  Obviously that's a harder problem (and
may be whether VLAs are used or not), and probably needs a
more powerful mechanism to be used safely.

So the mechanism I suggested, even though I think it does
fairly well for an important subset of the situations
involved when using VLAs, does address only a subset,
and a more general or more powerful mechanism would
be needed to handle cases like the ones you describe.

So now here is my question for you - what might such
a more general, more powerful, mechanism be?

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

#23094

Tim Rentsch <txr@alumni.caltech.edu> writes:
>  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.)

Phil
-- 
> I'd argue that there is much evidence for the existence of a God.
Pics or it didn't happen.
-- Tom (/. uid 822)

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

#23119

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

> Tim Rentsch <txr@alumni.caltech.edu> writes:
>>  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...

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

#23161

Tim Rentsch <txr@alumni.caltech.edu> writes:
> Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:
> > Tim Rentsch <txr@alumni.caltech.edu> writes:
> >>  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)

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

#23184

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

> Tim Rentsch <txr@alumni.caltech.edu> writes:
>> Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:
>> > Tim Rentsch <txr@alumni.caltech.edu> writes:
>> >>  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.

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

#23198

In article <kfn8vev1hrs.fsf@x-alumni2.alumni.caltech.edu>,
Tim Rentsch  <txr@alumni.caltech.edu> wrote:

[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?

-- 
Alan Curry

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

#23200

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.

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

#23208

In article <jtbr6n$mbn$1@speranza.aioe.org>,
jacob navia  <jacob@jspamsink.org> wrote:
>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.

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.

-- 
Alan Curry

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

#23218

pacman@kosh.dhis.org (Alan Curry) writes:

> In article <jtbr6n$mbn$1@speranza.aioe.org>,
> jacob navia  <jacob@jspamsink.org> wrote:
>>Le 08/07/12 04:54, Alan Curry a @C3{A9}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.
>
> 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?

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

#23222

In article <kfnehok7r83.fsf@x-alumni2.alumni.caltech.edu>,
Tim Rentsch  <txr@alumni.caltech.edu> wrote:
>pacman@kosh.dhis.org (Alan Curry) writes:
>>
>> 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

-- 
Alan Curry

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

#23228

pacman@kosh.dhis.org (Alan Curry) writes:

> In article <kfnehok7r83.fsf@x-alumni2.alumni.caltech.edu>,
> Tim Rentsch  <txr@alumni.caltech.edu> wrote:
>>pacman@kosh.dhis.org (Alan Curry) writes:
>>>
>>> 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.

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

#23206

pacman@kosh.dhis.org (Alan Curry) writes:

> In article <kfn8vev1hrs.fsf@x-alumni2.alumni.caltech.edu>,
> Tim Rentsch  <txr@alumni.caltech.edu> wrote:
>
> [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.

[toc] | [prev] | [standalone]

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

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

csiph-web