Thanks to them being yet another attack vector and funny stuff like on this post, got demoted to optional on C11.
Additionally Google spent several years paying to clean up the Linux kernel from all VLA occurrences.
Additionally Google spent several years paying to clean up the Linux kernel from all VLA occurrences.
Sadly, the C committee doesn't really understand what was wrong with VLAs and a sizable group of its members wants to make them mandatory again:
https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2921.pdf ("Does WG14 want to make VLAs fully mandatory in C23")
That's a mute point for C's target audience because they already understand that they need to be mindful of what the language does.
No, it's like saying that professional people understand the need to learn what their tools of the trade do beyond random stackoverflow search on how to print text to stdout.
It seems you have an irrational dislike of C. That's perfectly ok. No need to come up with excuses though.
Ever since I got my hands on Turbo C++ 1.0, back in 1993, I see no reason why one should downgrade ourselves to C.
At least C++ give us the tools to be a bit more secure, even if tainted with C's copy-paste compatibility.
You will find posts from me on Usenet, stading on C++ frontline of C vs C++ flamewars.
No one is making excuses, it should be nuked, unfortunely it will outlive all of us.
Personally, I haven't come across anyone who pronounces 'mute' without the /j/.
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.
Maybe. If the architecture supports protected memory and the compiler has placed an appropriately sized guard page below the stack. If it doesn't then overflowing the stack via a VLA gives you easy read and write access to any byte in program memory.
https://en.wikipedia.org/wiki/Stack_buffer_overflow
so, pretend I said "overflow" instead of "smash" in my post.
f (size_t n)
{
char str[n];
However the main reason we forbid VLAs in all our code is because thread stacks (particularly on 32 bit or in kernel) are quite limited in depth and so you want to be careful with stack frame size. VLAs make it harder to compute and thus check stack frame sizes at compile time, making the -Wstack-usage warning less effective. Large arrays get allocated on the heap instead.
https://msrc-blog.microsoft.com/2019/07/16/a-proactive-appro...
https://research.google/pubs/pub46800/
https://support.apple.com/guide/security/memory-safe-iboot-i...
Maybe you could give an helping hand to Microsoft, Apple and Google, they are in need of carefull C coders.
Personally, I don't use them, but I don't find "they're unsafe" to be a convincing reason for why they shouldn't be included in the already-unsafe language. Saying they're unnecessary might be a better reason.
That means there are a lot of not careful enough developers (AKA, human ones) that will write a lot of C just because they need some change here or there.
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.
The same is true for most recursive calls, should recursion be also banned in programming languages?
None of this applies to VLA arguments.
Nothing about it is "immensely complicated". Rather than store your recursion state in a call stack, you can store it in a stack of your own, i.e. a heap-allocated container. The state of a cycle of foo(a,b,c) -> bar(d,e,f) -> baz(g,h) -> foo(...) becomes expressible as an array of tagged union of (a,b,c), (d,e,f) and (g,h).
And there is nothing inherently unmaintainable about this approach. I would hope that it's a commonly taught pattern, but even if it's not, that doesn't make it impossible to understand. Picking good names and writing explanatory comments are 90% of the battle of readability.
> which is why something like Stockfish doesn't do that in its recursive search function even though the code base is extremely optimised
I can't speak for what Stockfish devs do, as I have no insight into which particular developers made what set of tradeoffs in which parts of their codebase. But it doesn't change the reality that using your own stack container is almost always more performant and more extensible:
1. Your own stack container can take up less space per element than a call stack does per stack frame. A stack frame has to store all local variables, which is wasteful. The elements of your own stack container can store just the state that is necessary.
2. Your own stack container can recurse much farther. In addition to the previous point, call stacks tend to have relatively small memory limits by default, whereas heap allocations do not. In addition, you can employ tricks like serializing your stack container to disk, to save even more memory and allow you to recurse even farther.
3. Your own stack container can be deallocated, shrunk, or garbage collected to free memory for further use, but a call stack typically only grows.
4. Your own stack container can be easily augmented to allow for introspection, which would require brittle hackery with a traditional call stack. This can be an extremely useful property, e.g. for a language parser resolving ambiguities in context sensitive grammars.
> And yes, some algorithms are inherently recursive, and don't gain any meaningfull performance from the heap stack + state machine approach.
Using a heap-allocated stack container is recursion. It is the state machine. The only fundamental implementation difference between the approach I describe and traditional recursion is that the former relies on the programmer using an array of algorithm state, and the latter relies on the runtime using an array of stack frames.
1. This is often irrelevant, depending on your priorities. Taking stockfish as an example again, memory is not what's at a premium, search nodes is. The search space is inherently intractable. You're never gonna be able to recurse meaningfully deeper by shaving off some stack space, because the breadth of the tree grows exponentially in the number of plies. The only form of optimisation that helps here is caching and various heuristics to avoid searching certain nodes at all
2. You know you can change the stack size, right? This is what Stockfish does for its search threads. No need for fancy dynamic allocation here. Also, have fun watching shit get interesting interesting when you have to realloc() ncpu huge chunks of contiguous memory balls deep into a search, when the engine is in time trouble... Sometimes resizing allocated memory is simply not an option.
3. Again this is not always relevant. Stockfish needs its big stacks all the time. So big whoop.
4. This Stockfish does need to do, which is why it keeps an array of structs(never resized) for that purpose. But Stockfish also needs to make decisions about when things move between the different stacks, which is why it uses recursive calls despite having a stack on the heap also.
5. It's obvious I am aware of this. My original comment literally said that banning recursion would force you to implement recursion manually anyway using a state machine. Like, dude, you're literally repeating my own comment back at me as if I didn't already know it. What's up with that?
The point here is: yes, in some specialised cases it might be preferable to implement the recursion yourself if the problem calls for it. But other times, and I'd argue most of the time, this is not necessary. So just use the already available abstraction provided by language. Your line of reasoning is a bit like arguing for not using C at all, because it will be slower than assembly in some cases. sure, write hand optimised assembly in your hot paths if you need to, but most people don't. Abstractions are generally our friends, they help us write clearer, more consise code.
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.
This is also ignoring the fact that the memory usage for recursive algorithms is higher because there’s a bunch of state for doing the function call being pushed onto the stack that you just don’t see (return address, potentially spilling registers depending on the compiler’s ability to optimize, etc). Unless you stick with tail recursion but that’s just a special case where the loop method would be similarly trivial. Case in point. I implemented depth first search initially as a recursive thing and blue out the stack on an embedded system. Switched to an iterated depth first search with no recursion. No problem.
OP said “it’s the only way to solve certain problems”. That’s clearly not true because ALL recursive algorithms can be mapped to non recursive versions.
I never got the fascination with implicit recursion. It’s just a slightly different way to express the solution. Personally I find it usually harder to follow / fully understand than regular iterative methods that describe the recursion state explicitly (ie time and space complexity in particular I find very hard to reason about for recursion.)
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.
Targeting the standard is nice, but if all of your target platforms guarantee certain behaviors, you might consider using those. A lot of UB in the C standard is perfectly defined and consistent across MSVC, GCC, Clang, and ICC.
Do you have examples of this "a lot of UB in the C standard" which is in fact guaranteed to be "perfectly defined and consistent" across all the platforms you listed ? You may need to link the guarantees you're relying on.
My GCC offers to turn signed integer overflow into either an abort or wrapping, either of which is defined behaviour, but how do I get MSVC to do precisely the same thing?
Likewise for aliasing rules. GCC has a switch to have the optimiser not assume the language's aliasing rules are actually obeyed, but what switch in MSVC does exactly the same thing?
I once had a bug like that in a piece of AVR C code where the stack corruption would happen in the same place every time and the code would pathologically jump to the same places in the same order every time. It's worth noting though that when there's an OS, usually what will happen is just a SIGABRT. See the OpenBSD libc allocator for a masterclass in making misbehaving programs crash.
I was never advocating to rely on UB, btw. But yes, UB can be understood in many cases.
Avoiding UB (edit: in general) doesn't have anything to do with the code being portable and everything with the code not being buggy [1][2].
[0] https://en.cppreference.com/w/c/language/behavior
[1] https://blog.regehr.org/archives/213
[2] http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
You cite to a source that contradicts you. In the llvm blog post: "It is also worth pointing out that both Clang and GCC nail down a few behaviors that the C standard leaves undefined."
Added 'in general' to my comment to make this explicit.
According to wikipedia "C11 does not explicitly name a size-limit for VLAs"
But what if the length of your variable length array is, say, gigabytes, you've blown way past the guard pages, and your pointer is now in non-stack kernel land.
You'd have to check the stack pointer all the time to be sure, that's prohibitive performance-wise. Ironically, x86 kind of had that in hardware back when segmentation was still used.
But that's not my point. If the compiler/runtime knows it will blow up if you have an allocation over 4KB or so, then it needs to do something to mitigate or reject allocations like that.
What exactly are you doing there, in kernel code?
> But that's not my point. If the compiler/runtime knows it will blow up if you have an allocation over 4KB or so, then it needs to do something to mitigate or reject allocations like that.
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.
It's not impossible and mitigations exist, but it is pretty "extra". gcc has -fstack-check that (I think) does something there.
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 pages. You don't need to know the stack size or have any bookkeeping to do that, you just prod a byte every page_size. And you only need to do that for allocations that are very big. In normal code it's just a single not-taken branch for each VLA.
"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
* 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.
Speaking seriously, I too would like an answer.
[0] https://docs.microsoft.com/en-us/windows/win32/devnotes/-win...
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.
Triggering use of the injected code may require another call timed precisely to hit the changed code before the page fault occurs.
Of course, the compiler could and should check for stack allocations that may jump over guard pages and abort the program (or, if in a syscall, the OS) or grow the stack when needed. Also, VLAs aren’t needed for this. If the programmer creates a multi-megabyte local array, this happens, too (and that can happen accidentally, for example when increasing a #define and recompiling)
The lesson is, though, that guard pages alone don’t fully protect against such attacks. The compiler must check total stack space allocated by a function, and, if it can’t determine that that’s under the size of your guard page, insert code to do additional runtime checks.
I don’t see that as a reason to outright ban VLAs, though.
int A[100000000];
exhibit A: https://lists.freedesktop.org/archives/mesa-commit/2020-Dece...
exhibit B: https://github.com/neovim/neovim/issues/5229
exhibit C: https://github.com/sailfishos-mirror/llvm-project/commit/6be...
etc etc
#include <cstdlib>
#include <span>
__attribute__((annotate("realtime")))
void process_floats(std::span<float> vec)
{
auto filter = (float*) malloc(sizeof(float) * vec.size());
/* fill filter with values */
for(int i = 0; i < vec.size(); i++)
vec[i] *= filter[i];
free(filter);
}
$ stoat-compile++ -c foo.cpp -emit-llvm -std=c++20
$ stoat foo.bc
Parsing 'foo.bc'...
Error #1:
process_floats(std::span<float, 18446744073709551615ul>) _Z14process_floatsSt4spanIfLm18446744073709551615EE
##The Deduction Chain:
##The Contradiction Reasons:
- malloc : NonRealtime (Blacklist)
- free : NonRealtime (Blacklist)
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 array is 16. Is there room for 32? It's 32.
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?
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.
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!)
`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.
As I see it, it leads to a contradiction. `cat` have unbounded time of execution. It depends on a size of input. It means that `cat` cannot be realtime. But this logic leads us to a conclusion, that any OS kernel cannot be realtime, because it works for an unbounded time.
It is a non sense. Realtime is about latency: how much it takes time to react to an input. `cat` may be realtime or may be not, it depends on how we define "input". We need to define it in a way that it is bounded. I mean 4Kb chunks of bytes for example.
> Like your function might receive an arbitrarily large n-element array a[] and just return a[a[n-1]], and it would be constant time.
No. Receiving n-element array is an O(n) operation. It needs to be copied to memory. We can of course pick one function that just get a pointer to an array, but if real-time is a property of the whole system, then this system needs to copy the array from the outside world into memory. And it is an O(n) operation. So for any latency requirement exists such N so when n>N this requirement would not be met. So unbounded array as an input is incompatible with a real-time.
I think that's basically what the LLVM SafeStack pass does -- stack variables that might be written out of bounds are moved to a separate stack so they can't smash the return address.
I imagine you could you allocate it at the same time as you allocate the thread's own stack?
that's in most systems I target a run-time property, not a compile-time one
What does 'mandatory' mean? Like if I write a C compiler without them... what are they going to do about it?