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

211–220 of 257 posts

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

#211

Post by Joker_vD »

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

Because it's on by default in MSVC [0], and we all know that whatever technical decisions MS makes, they're superior to whatever technical decision the GNU people make. /s

Speaking seriously, I too would like an answer.

[0] https://docs.microsoft.com/en-us/windows/win32/devnotes/-win...

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

#212

Post by naasking »

Dylan16807 wrote: post #191
bjourne wrote: post #186

Earlier quoted context omitted.

An attacker would first trigger a large VLA-allocation that puts the stack pointer within a few bytes of the guard page. Then they would just have the kernel put a return address or two on the stack and that would be enough to cause a page fault. The only way to guard against that would be to check that every CALL instruction has enough stack space which is infeasible.

But that's the entire point of the guard page, it causes a page fault. That's not corruption. Denial of service by trying to allocate something too big for the stack is obvious. I'm asking about how corruption is supposed to happen on a reasonable platform.

Perhaps they're trying to guard against introducing easy vulnerabilities on unreasonable platforms. With VLAs unskilled developers can perhaps more easily introduce this problem. It would be a case of bad platforms and bad developers ruining it for the rest.

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

#213

Post by naasking »

astrange wrote: post #198
_0w8t wrote: post #131

Earlier quoted context omitted.

VLAs are unsafe in the worst kind of way as it is not possible to query when it is safe to use them. alloca() at least in theory can return null stack overflow, but there is no such provision with VLA.

They're not unsafe (in the memory sense) as long as they check for overflow and reliably crash if there is one.

If a lot of platforms don't implement this check reliably, then it's unsafe in practice at this time, even if not in theory.

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

#214

Post by camel-cdr »

GabrielTFS wrote: post #170
camel-cdr wrote: post #41

This is only tangential to the article: C isn't Turing complete without `fseek` (as far as I can tell). Turing completes requires you to be able to read/write from an infinite tape (essentially infinite memory). This isn't possible in C, because `sizeof` is a constant expression, thus limiting the size of any type, and importantly also pointer type, to a finite number, thus making the addressable memory finite. From…

If you want to talk about this kind of technicality, here are three other avenues through which I believe Turing completeness of C can be achieved: 1. As https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm helpfully points out, "If two objects have identical bit-pattern representations and their types are the same they may still compare as unequal", and "[implementations] may also treat pointers based on diff…

Let me address 2. and 3. first, because 1. is probably correct.

2. The problem with that is that you may have infinite recursion, but you can only pass finite amounts of memory between recursion steps. This has also been addressed by https://cs.stackexchange.com/a/60978.

3. I don't follow, how could you create a growing `va_list`?

Edit: Actually, I think I do now, so you essentially create a sort of linked list of `va_list`s?

1. This is probably correct. You'd need to be able to round trip through a void*, but that could still be implemented to retain the tagged data. I thought of pointer tagging more in terms of marking addresses with certain memory protection properties, but what you suggest should be possible. There may still be some wording disallowing it, but I couldn't find it.

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

#215

Post by jcelerier »

dataflow wrote: post #125
tedunangst wrote: post #123

Earlier quoted context omitted.

Here's a nickel, kid. The bullshit about oh my embedded systems doesn't have dynamic memory is bullshit. You either know how big your stack is and how many elements there are, and you make the array that big. Or you don't know and you're fucked. You can't clever your way out of not knowing how big to make the array with magic stack fairy pretend dynamic memory. You can only fuck up. Is there room for 16 elements? The…

I think the parent comment was about malloc not being real-time? Not about storage space. Though I do wonder why there can't be a form of malloc that allocates in a stack like fashion in real time to satisfy the formal verifier?

how would you implement that in the face of multiple threads? you can't use TLS as it will have initialize your stack on first access of your malloc_stack in a given thread, which may or may not be safe to use in real-time-ish-contexts (I think it's definitely not on Windows, not sure on Linux)

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

#216

Post by dataflow »

jcelerier wrote: post #215
dataflow wrote: post #125

Earlier quoted context omitted.

I think the parent comment was about malloc not being real-time? Not about storage space. Though I do wonder why there can't be a form of malloc that allocates in a stack like fashion in real time to satisfy the formal verifier?

how would you implement that in the face of multiple threads? you can't use TLS as it will have initialize your stack on first access of your malloc_stack in a given thread, which may or may not be safe to use in real-time-ish-contexts (I think it's definitely not on Windows, not sure on Linux)

> how would you implement that in the face of multiple threads?

I imagine you could you allocate it at the same time as you allocate the thread's own stack?

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

#217

Post by msla »

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.

> It's not strictly necessary precisely because all recursions can be "simulated" with a heap allocated stack.

This just moves the problem from a stack blowout to a heap blowout.

> And in fact, the "simulated" approach is almost always better, from both a performance and a maintenance perspective.

I am unsure about the performance, but turning recursive code implementing a recursive procedure into iterative code which has to maintain a stack by hand cannot possibly improve readability unless the programmers involved are pathologically afraid of seeing recursive code.

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

#218

Post by ordu »

dataflow wrote: post #157
kllrnohj wrote: post #155

Earlier quoted context omitted.

Real time also generally means your input sizes are bounded and known, otherwise the algorithm itself isn't realtime and malloc isn't the reason why. But strictly speaking the only problem is a malloc/free that can lock (you can end up with priority inversion). So a lock-free malloc would be realtime just fine, it doesn't have to be stack growth only.

> Real time also generally means your input sizes are bounded and known, otherwise the algorithm itself isn't realtime and malloc isn't the reason why. I think you meant to say something else? Real-time is a property of the system indicating a constraint on the latency from the input to the output—it doesn't constrain the input itself. (Otherwise even 'cat' wouldn't be real-time!)

If your input is not bounded you can't know in advance the time needed to process it. In other word you cannot be realtime.

`cat` can be realtime, but only by fixing the size of its internal buffer where it reads to and writes from. In this case it can in theory bound the time needed to process the fixed block of input.

But if for some reason `cat` tried to read/write by lines of unknown in advance size, it would fail to be realtime.

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

#219

Post by dataflow »

ordu wrote: post #218
dataflow wrote: post #157

Earlier quoted context omitted.

> Real time also generally means your input sizes are bounded and known, otherwise the algorithm itself isn't realtime and malloc isn't the reason why. I think you meant to say something else? Real-time is a property of the system indicating a constraint on the latency from the input to the output—it doesn't constrain the input itself. (Otherwise even 'cat' wouldn't be real-time!)

If your input is not bounded you can't know in advance the time needed to process it. In other word you cannot be realtime. `cat` can be realtime, but only by fixing the size of its internal buffer where it reads to and writes from. In this case it can in theory bound the time needed to process the fixed block of input. But if for some reason `cat` tried to read/write by lines of unknown in advance size, it would fai…

I think we're not disagreeing on the actual constraints, but the terminology. The "internal buffer" is not part of the system's "input". It's part of the system's "state".

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

#220

Post by Banana699 »

asguy wrote: post #159
Banana699 wrote: post #148

Earlier quoted context omitted.

A JS runtime is a lot more than the core engine, or else nodejs is just a thin wrapper over V8 as well, which is obviously absurd. So without a count of the source lines for each language's portion of the implementation (very rough but acceptable first approximation of how much is implemented in each), you can't claim C++ is doing most of the heavy lifting and be taken seriously. PS. the worst C++ code is still a hel…

Quoted post unavailable.

The only one coping here is that who doesn't understand VMs and language research enough and retreats into childish "it was just a joke lol" remarks when out of their depth.

Incidentally, I write all 3 of C, C++ and x86 assembly, which is why I understand how braindead and unfit for human usage they are.

Post reply on HN