12 ms·
The Linux Kernel Is Now VLA (Variable-Length Array) Free
- wiz21c 8y agoFTA : >>> - VLAs within structures is not supported by the LLVM Clang compiler and thus an issue for those wanting to build the kernel outside of GCC, Clang only supports the C99-style VLAs. one less vendor lock in (but since it's GCC, it makes me sad).
- z3t4 8y agoMeanwhile on the web ...
- pjmlp 8y agoThankfully! VLAs were a very dumb idea to start with, given C's sematics.
- krzyk 8y agoWhy? It has quite nice simple syntax. And all C newbies love it (doing malloc and then free is cumbersome, and not needed in simple cases).
- pjmlp 8y agoWhat about lack of bounds checking leaving the door open to security exploits, in the days where CVEs caused by C's use increase every month?!? Hence why they were dropped in C11. Being an optional annex means that actually most C vendors won't bother.
- delinka 8y agoSo C's VLA feature has been implemented on stack space. Why not on the heap? Seems safer. Is this strictly about convenience for implementation? Reclaiming stack memory at the end of the scope is already implemented, so I understand the motivation. What I don't understand is: after all these decades of stack smashing vulnerabilities, why would such a shortcut have been taken? Convenience costs performance, safety costs performance ... at some point you just have to suck it up and pay the performance penalty to make things safer and to improve programmer productivity.
- lstodd 8y agoBecause there might not be a heap at all.
- castratikron 8y agoStack allocation is easier to implement and faster than heap allocation. The former can be implemented in a single instruction (incrementing the stack pointer).
- palotasb 8y agoI'd guess because VLA on the heap already existed and it's called malloc. The only difference would be free() being called automatically but that is not something the C standard would do lightly.
- drfuchs 8y agoYou'd have to get longjmp to understand how to unwind these heap-allocated arrays, not only from the current function's stack frame, but for all the ones in the longjmp'd-over frames. In C-land, longjmp simply overwrites the stack pointer (and all other registers), which implicitly "deallocates" all the VLA arrays, and all alloca() allocations, in one fell swoop. There is no notion of a step-by-step unwinding of the stack, so it would be a big task to try to trap all intermediate VLA arrays.
- lclarkmichalek 8y agoGod bless Kees Cook
- chris_wot 8y agoOk, I’ve looked but failed - where is there an example of what a VLA is?
- nwmcsween 8y agoint foo[n] where n is variable and cannot be inferred at compile time.
- asveikau 8y agovoid foo(int n) { int m[n]; } The downside is if n is large you use a lot of stack, but you wouldn't notice if it's mostly called with low values. So a bit of a ticking time bomb. I guess if you have a really large n, like more than a few pages worth, then certain values of m[i] might wind up in some other page allocation where it shouldn't.... I seem to recall a vulnerability like this a year or two ago. (Normally a stack can grow on a page fault by hitting a guard page, but if the n above is absurdly large...)
- krzyk 8y agoOK, so what's the difference between that and malloc'ing a too big value? Same issue, you just need larger values. In both cases you need a guard.
- notacoward 8y agoThere's a huge difference in stack vs. heap allocations. Stack space might be effectively infinite in the basic user-space world, but not in any environment using green threads and certainly not in the kernel. In the Linux kernel this is made far worse by the fact that each task's stack sits right above the task structure itself, so a huge allocation might smash the task structure or the next task's stack. The latter is exactly what I had to debug a couple of jobs ago, and it was one of the more difficult debugging journeys of my long career (it was quite sporadic and manifested as hard hangs). VLAs make that kind of scenario much more likely. Being able to check the length before a potentially disastrous allocation is cumbersome, but safer.
- ericpauley 8y agoCurious that there isn't a static analysis to verify that these have been removed completely. Is this difficult or was it just not worth the effort?
- kbumsik 8y agoI think VLA becomes a compiler feature. We can disable VLA using a GCC option flag: -Werror=vla. So it should be quite easy to detect if VLA is used in the source.
- bonyt 8y agoI think they mean it’s removed for most of the modules in the kernel and therefore the ones that may be lurking about still aren’t being compiled on most configurations. According to the article, “there may be a couple more VLAs hiding in hard-to-find randconfigs.”
- ndesaulniers 8y agoThe hard part with the kernel is its fanciful build system, Kbuild. It's great at turning off compilation of subsystems that you don't plan to use. The difficulty is that there are a large number of mutually exclusive number of configurations, so the config that's called `allyesconfig` really isn't "all" because you can only pick one of the mutually exclusive configs. Additionally, some configs don't just add/remove code, but can change which implementation gets compiled in (all via C preprocessor and -D flags). Those configs mean there are massive combinations of what is actually set, and which code you're actually trying to compile. I imagine that's similarly difficult for static analysis; due to the build system and what code you run it over. I think a simpler approach with grep might actually work better.
- woodruffw 8y agoAwesome. I'm looking forward to the day that the Linux kernel stops using the (GNU-specific) `sizeof(void) == 1` assumption as well[1]. [1]: Just by way of example, one that I ran into recently: https://elixir.bootlin.com/linux/latest/source/include/uapi/linux/netfilter/x_tables.h#L129 https://elixir.bootlin.com/linux/latest/source/include/uapi/...
- ndesaulniers 8y agoIs there a call site that passes void to that macro?
- nwellnhof 8y agoYou don't have to pass void to sizeof explicitly (which, by the way, is an operator, not a macro). The typical use case is arithmetic on void pointers, for example: void f(void *buf) { // Clear bytes 10-19 memset(buf + 10, 0, 10); } Making void pointers behave like char pointers avoids pointer casts in cases like this.
- millstone 8y agoWhy? It's useful for pointer arithmetic and seems harmless, since the alternative is to make it an error. It would be better for the C spec to just define sizeof(void) == 1.
- sleavey 8y agoI am ignorant of this particular aspect of C and most of C in general, but shouldn't the kernel developers try to follow the C standard instead of just a compiler's?
- int0x80 8y agoThe C standard covers a lot of details and cases that the kernel doesn't need to worry about. That makes the C standard a lot more restricted and constrained. GNUC has some convenient features and extensions because it makes assumptions not guaranteed by the C standard that happen to work for all the platforms that Linux cares about, and also, not beeing driven by a comittee, it can generally iterate and improve the language in a more agressive and fast way.
- kristianp 8y agoAre there any numbers as to what difference this will make to the compiled size and speed of the kernel? I imagine the difference in size will be tiny. Did they profile before optimising[1] and identify it as a problem? [1] http://wiki.c2.com/?ProfileBeforeOptimizing http://wiki.c2.com/?ProfileBeforeOptimizing
- gbear605 8y agoAccording to the article, this is in large part for security, and a little bit for speed, not for size.
- kristianp 8y agoThere is a Linus quote in the article: "It generates much more code, and much _slower_ code (and more fragile code),". "generates much more code" means a size difference.
- rstuart4133 8y agoIf he had just said what you quoted he would be wrong in the general case. He actually said it is all those things in comparison to doing fixed allocation. The reason that is relevant is the kernel stack is so small you can only use a VLA when you know in advance the upper bound on the size is small, but if it's small you may as well use the fixed upper bound, and if you do that it is always faster, smaller and less fragile than using a VLA. He's wrong in the general case, because user land C programmers will replace a VLA with: if (!(array = malloc(n * sizeof(array[0]))) fatal("I'm out of memory"); which compared to the VLA generates more code and is slower. In both the VLA and malloc() case if you run out of memory the program will die nice and deterministically (unlike the kernel), but in the malloc() case that will only happen if you remember to do the check whereas in the VLA case the compiler ensures it always happens.
- Fronzie 8y agoWasn't removal of VLA also a requirement for building the kernel with clang/llvm ? Does this mean that mainline now builds with llvm?
- larkeith 8y agoThough much less strict, this brings to mind the JPL Coding Standard for C [1] - it seems like a similar idea as a lot of JPL's rules, in that it is much more difficult to verify and ensure the stability of less static data structures; compare: 3: Use verifiable loop bounds for all loops meant to be terminating [1] https://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf https://lars-lab.jpl.nasa.gov/JPL_Coding_Standard_C.pdf
- carlmr 8y agoVerifiable doesn't mean static. You could have VLA with an upper bound and still not violate this rule.
- int_19h 8y agoI'm actually kinda sad that VLAs didn't work out in general (they have been downgraded to an optional feature in the latest C standards). For all the downsides, they make working with matrices in C much easier.
- enriquto 8y agoYeah, VLA is one of my favorite features in C. I would love if it was viable to use them for arbitrarily large temporary arrays. They lead to much cleaner code. Instead of { float *x = malloc(n * sizeof*x); ... free(x); } you do simply { float x[n]; ... } In image processing, you often need large temporary images, but it is dangerous to distribute code such as the above unless you play with the stack limits from outside your program.
- dzdt 8y agoIts unfortunate that C and C++ kept the mindset that automatically memory managed variables are stored on a SMALL stack, with the consequence of exceeding that small and unknown size being that your program crashes. For variable sized arrays, there is already a bit of overhead in sizing the allocation. Would it really have been impossible to move large allocations to the heap with automatic free at exit of the scope?
- maxlybbert 8y agoC++ has std::vector, which doesn’t have any implicit size limitations. I haven’t kept up with the details, so this may have changed, but during the discussions for what C++11, the committee decided not to include VLAs in the official standard because the library already included std::vector.
- int_19h 8y agoThe problem with vector is that it always heap-allocates. The ideal approach is the one where small allocations are on the stack, and large ones are on the heap, without the API user having to do anything about it. C++ has had a proposal for std::dynarray floated for a while, which would basically have semantics allowing stack allocation, but wouldn't mandate it, leaving it as a quality of implementation issue (so it would be legal to implement it on top of vector, but it was assumed that compilers would go for optimizations given the opportunity). It didn't pass, unfortunately.