Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

C99 doesn't need function bodies, or 'VLAs are Turing complete'

lemon.rip

Post reply on HN
Print view View original

171–180 of 257 posts

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#171

Post by tialaramex »

mtlmtlmtlmtl wrote: post #152
petters wrote: post #146

Earlier quoted context omitted.

Welcome to the world of undefined behavior. Anything can happen....

I think this is a common misunderstanding about UB. It's not that anything can happen, just that the standard doesn't specify what happens, meaning whatever happens is compiler/architecture/OS dependent. So you can't depend on UB in portable code. But something definite will happen, given the current state of the system. After all, if it didn't, these things wouldn't be exploitable either.

> But something definite will happen, given the current state of the system.

This is only true in the very loose and more or less useless sense that the compiler is definitely going to emit some machine code. What does that machine code do in the UB case? It might be absolutely anything.

One direction you could go here is you insist that surely the machine code has a defined meaning for all possible machine states, but that's involving a lot of state you aren't aware of as the programmer, and it's certainly nothing you can plan for or anticipate so it's essentially the same thing as "anything can happen".

Another is you could say, no, I'm sure the compiler is obliged to put out specific machine code, and you'd just be wrong about that, Undefined Behaviour is distinct from Unspecified Behaviour or merely Platform Dependant behaviour.

Many C and C++ programmers have the mistaken expectation that if their program is incorrect it can't do anything really crazy, like if I never launch_missiles() surely the program can't just launch_missiles() because I made a tiny mistake that created Undefined Behaviour? Yes, it can, and in some cases it absolutely will do that.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#172

Post by Dylan16807 »

anyfoo wrote: post #169
Dylan16807 wrote: post #168

Earlier quoted context omitted.

> What exactly are you doing there, in kernel code? In kernel code? What you're doing is triggering the guard page over and over if the stack is pushing into new territory. > Do what exactly? Just reject stack allocations that are larger than the cluster of guard pages? And keep book of past allocations? A lot of that needs to happen at runtime, since the compiler doesn't know the size with VLAs. Just hit the guard p…

That seems to be what -fstack-check for gcc is doing: "If neither of the above are true, GCC will generate code to periodically “probe” the stack pointer using the values of the macros defined below."[1] I guess I'm wondering why this isn't always on if it solves the problem with negligible cost? Genuine question, not trying to make a point. [1] https://gcc.gnu.org/onlinedocs/gccint/Stack-Checking.html

What I'm finding in a quick search is:

* It should be fast, but I haven't found a benchmark.

* There appear to be some issues of signals hitting at the wrong time vs. angering valgrind, depending on probe timing.

* Probes like this are mandatory on windows to make sure the stack is allocated, so it can't be that bad.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#173

Post by GabrielTFS »

camel-cdr wrote: post #156
Phrodo_00 wrote: post #154

Earlier quoted context omitted.

Speaking in so much the abstract that it becomes absurd (which also can be used to prove your point, but bear with me here), since `size_t` is required to hold the size of any object, and a turing machine has infinite memory, then size_t would also need to be infinitely big, and `sizeof(size_t)` would be a constant returning infinity. So, I don't think it having to be a constant is a problem as much as having to deal…

I don't think infinitely large integer constant area construct that makes sense. As far as I'm aware, there isn't an instance of an infinitely large integer, even in mathematics, there are finite integers and there is the concept of infinity. (And size_t is defined as an unsigned integer type)

I'd argue you could use non-standard integers that are unable to be reached in a finite amount of steps but aren't infinity and are still "integers".

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#174

Post by anyfoo »

Dylan16807 wrote: post #172
anyfoo wrote: post #169

Earlier quoted context omitted.

That seems to be what -fstack-check for gcc is doing: "If neither of the above are true, GCC will generate code to periodically “probe” the stack pointer using the values of the macros defined below."[1] I guess I'm wondering why this isn't always on if it solves the problem with negligible cost? Genuine question, not trying to make a point. [1] https://gcc.gnu.org/onlinedocs/gccint/Stack-Checking.html

What I'm finding in a quick search is: * It should be fast, but I haven't found a benchmark. * There appear to be some issues of signals hitting at the wrong time vs. angering valgrind, depending on probe timing. * Probes like this are mandatory on windows to make sure the stack is allocated, so it can't be that bad.

I'm mostly interested in it for kernel code though, so the second point at least does not apply, at least not directly. Maybe there is something analogous when preempting kernel threads, I haven't thought it through at all. But interesting.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#175

Post by saagarjha »

10000truths wrote: post #162
mtlmtlmtlmtl wrote: post #149

Earlier quoted context omitted.

That's not really a fair comparison though. Recursion is strictly necessary to implement several algorithms. Even if "banned" from the language, you would have to simulate it using a heap allocated stack or something to do certain things. None of this applies to VLA arguments.

It's not strictly necessary precisely because all recursions can be "simulated" with a heap allocated stack. And in fact, the "simulated" approach is almost always better, from both a performance and a maintenance perspective.

Definitely not.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#176

Post by saagarjha »

lelanthran wrote: post #127
jasonhansel wrote: post #124

Earlier quoted context omitted.

Doesn't a similar DoS risk (from allowing users to allocate arbitrarily large amounts of memory) also apply to the heap? You shouldn't be giving arbitrary user-supplied ints to malloc either.

> Doesn't a similar DoS risk (from allowing users to allocate arbitrarily large amounts of memory) also apply to the heap? DoS Risk? No one cares too much about that - the problem with VLAs is stack smashing, which then allows aribtrary user-supplied code to be executed. You cannot do that with malloc() and friends.

VLAs don’t smash the stack.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#177

Post by saagarjha »

petters wrote: post #146
Dylan16807 wrote: post #144

Earlier quoted context omitted.

How does a huge VLA corrupt the stack? If there's not enough space but code keeps going then isn't that a massive bug with your compiler or runtime?

Welcome to the world of undefined behavior. Anything can happen....

The C standard has no mentions of a program stack. This isn’t undefined behavior.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#178

Post by saagarjha »

einpoklum wrote: post #44
planede wrote: post #38

Earlier quoted context omitted.

You can corrupt the stack without VLAs just fine. What else?

With VLAs: 1. The stack-smashing pattern is simple, straightforward and sure to be used often. Other ways to smash the stack require some more "effort"... 2. It's not just _you_ who can smash the stack. It's the fact that anyone who calls your function will smash the stack if they pass some large numeric value.

They can overflow the stack. They cannot smash the stack.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#179

Post by saagarjha »

TazeTSchnitzel wrote: post #83
beeforpork wrote: post #5

But why? Why is this VLA parameter defined this way? It seems totally bizarre and unnecessary, but I suppose it must have been added to the standard to solve some kind of problem? Is the proposal for this feature available and gives some insight?

Allowing arbitrary expressions allows self-documenting signatures: void concat_strs( int str1_len, const char str1[str1_len], int str2_len, const char str2[str2_len], char out_str[str1_len + str2_len], ); void manipulate_array( array_dim dim, int arr[dim.x][dim.y], ); Supporting things like printf() was probably not specifically desired, but it would be difficult to define it in such a way that it accepts all reasona…

Tip: if writing new functions that take things that are not strings, try to avoid C’s mistakes with strncpy and putting “str” in the name.

Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'

#180

Post by saagarjha »

pjmlp wrote: post #37
planede wrote: post #34

Earlier quoted context omitted.

What's wrong with VLAs is their syntax. It really shouldn't use the same syntax as regular C arrays, otherwise they would be fine, maybe with a scary enough keyword. They are more generic than alloca too, alloca being scoped to the function, while VLAs being scoped to the innermost block scope that contains them.

Syntax, no protection against stack corruption,...

VLAs are no more unsafe than standard C is for stack corruption.
Post reply on HN