«

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.

Eric Sosman <> writes:

> On 6/27/2012 8:50 AM, Ben Bacarisse wrote:
>> jacob navia <> writes:
>> <snip>
>>> lcc-win was ported to a 16 bit Analog Devices chip with something like
>>> 40K RAM available.
>>>
>>> There was no stack, and the stack was created by the compiler using
>>> a memory array: this implied a static analaysis.
>>>
>>> Recursion was forbidden (coudln't be analyzed well) and indirect
>>> recursion was detected: function A calls B that calls C that calls A.
>>
>> If recursion is forbidden, would it not be worthwhile having a single
>> static area for each function? This is what some IBM compilers used to
>> do (and they may still do for all I know).
>
> A shared stack would use less memory, unless there was some
> execution path in which all functions were active simultaneously.

Very true, and it seems that memory is scarce in this example so it's
not likely to worthwhile.

<snip>
--
Ben.

jacob navia <> writes:
>Le 27/06/12 18:36, Stefan Ram a écrit :
>>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.

Ok, I see.

(Possibly, sometimes a public

#define LIST_SIZE 104

can be made less error-prone, once one adds run-time assertions of

LIST_SIZE == sizeof PRIVATE_LIST

to the initialization function for the list package if
there is such an initialization function (that is not called
once per list initialization, but only once for each process
using the list package.)

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

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

Ian Collins <ian-> 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?

On 06/28/12 12:23 PM, Tim Rentsch wrote:
> Ian Collins<ian-> 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

Ian Collins <ian-> writes:

> On 06/28/12 12:23 PM, Tim Rentsch wrote:
>> Ian Collins<ian-> 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.

On 06/30/12 05:48 AM, Tim Rentsch wrote:
> Ian Collins<ian-> 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

בת×�ריך יו×� שבת,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 beallowed 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 thansegfault, and there's no real reason to slow down alloca().