What is the best alternative when I want to allocate some reasonably sized array on the stack and don’t want to always reserve the worst case size? alloca?
You don't need an alternative. VLAs are perfectly appropriate for that use case.
C99 doesn't need function bodies, or 'VLAs are Turing complete'
161–170 of 257 posts
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#162Earlier quoted context omitted.
> stuff like ... leads to a possible exploit where the input is manipulated so n is large The same is true for most recursive calls, should recursion be also banned in programming languages?
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.
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#163Earlier 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....
What is undefined about a large VLA? It shouldn't be undefined.
According to wikipedia "C11 does not explicitly name a size-limit for VLAs"
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#164Earlier 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?
> Though I do wonder why there can't be a form of malloc that allocates in a stack like fashion in 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.
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#165Earlier 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?
Okay. How do you tell the kernel that? Sure, the kernel will have put a guard page or more at the end of the stack, so that if you regularly push onto the stack, you will eventually hit a guard page and things will blow up appropriately. 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…
I think the normal pattern is a stack probe every page or so when there's a sufficiently large allocation. There's no need to check the stack pointer all the time.
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.
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#166Earlier quoted context omitted.
Okay. How do you tell the kernel that? Sure, the kernel will have put a guard page or more at the end of the stack, so that if you regularly push onto the stack, you will eventually hit a guard page and things will blow up appropriately. 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…
I think the normal pattern is a stack probe every page or so when there's a sufficiently large allocation. There's no need to check the stack pointer all the time. 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.
> I think the normal pattern is a stack probe every page or so when there's a sufficiently large allocation.
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.
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#167This kind of insanity is exactly why I don't use stuff like C anymore. It's a landmark and incredible language, but it's chock full of potholes and foot-shotguns (footguns that blow off your entire leg). Even huge companies can't get it right, which makes sense. It started as a language basically without guardrails, and because of the extreme deference to the holy backward compatibility, it's more or less always goin…
> It's a landmark and incredible language, but it's chock full of potholes and foot-shotguns (footguns that blow off your entire leg). There are very few footguns in C, compared to (say) C++ (or Python). I can guarantee you that no employed C developer is putting IOCCC type code into shipping products. Pick any language you like, and turn up the code golfing to 11, and you'll be equally horrified.
> Pick any language you like, and turn up the code golfing to 11, and you'll be equally horrified.
Challenge accepted. I pick the Go language, here are my answers:
https://codegolf.stackexchange.com/users/7815?tab=answers
people complain about how verbose Go is, but to me that just means its readable. Even golfed, its pretty clear what is going on.
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#168Earlier quoted context omitted.
I think the normal pattern is a stack probe every page or so when there's a sufficiently large allocation. There's no need to check the stack pointer all the time. 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.
> I think the normal pattern is a stack probe every page or so when there's a sufficiently large allocation. 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…
> 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 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.
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#169Earlier quoted context omitted.
> I think the normal pattern is a stack probe every page or so when there's a sufficiently large allocation. 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…
> 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
Re: C99 doesn't need function bodies, or 'VLAs are Turing complete'
#170This 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 different origins as distinct even though they are bitwise identical". It can thus be argued that, with a rather strict definition of provenance (i.e. how pointer values may be constructed), one could construct an implementation where every byte of every pointer is tagged with additional unbounded data that lets the whole pointer be properly dereferenced (I say every byte so that you're able to convert the pointer to an integer and convert it back to the same valid pointer), and where, as allowed by DR 260, pointers that have identical observable bit-pattern representations might not compare equal if they point to different objects. Thus, that implementation could create an unbounded amount of pointers.
2. Spawning off another thread and using infinite recursion (C has no defined recursion depth limit, and if you want to argue about automatic variables needing addresses or whatever and that the as-if rule doesn't cover that, there's `register` which makes address-less variables) to have two pushdown automatas that can together work as a Turing Machine.
3. Using variadic arguments. With `va_copy`, one can iterate through variadic arguments multiple times, and thus `va_list` can be used to implement a mechanism equivalent to pointers without actual pointers (any sane implementation probably uses a pointer for `va_list` somewhere in it, but that's not a problem here) and thus make a pushdown automata with 2 stacks