Re:Variable Length Arrays are problematic
by Animats on Monday July 05, 2021 @07:48PM
(#27742906)
Title should mention "in C". And that this is about kernel code.
The kernel has limited stack space and isn't good at growing it.
QNX got this right. No strings in the kernel. Everything is either fixed-length or in user space. A privileged program in user space deals with filenames and such.
Re:Variable Length Arrays are problematic
by josefx on Tuesday July 06, 2021 @01:32AM
(#27744535)
> A VLA is by definition on the stack
Do you have a source for that claim? The C11 standard notes that memory associated with a variable length array can be "squandered" by a longjmp, as far as I understand that shouldn't happen with stack allocation.
Most implementations may use stack allocation, leading to the stackoverflow problems described in the article. However as far as I can tell the standard doesn't require this.
Re:Variable Length Arrays are problematic
by unnah on Tuesday July 06, 2021 @02:38AM
(#27744909)
Right, VLA is not just syntactic sugar for alloca, it's also syntactic sugar for accessing and passing around multi-dimensional arrays. The latter two work perfectly fine with heap-allocated arrays.
In C89 the ability to pass multi-dimensional arrays to functions was not very useful, since the inner dimensions could not vary at runtime. Fixing this was the main point of the VLA feature, at least for people who work on array data. It would be even more useful, had they supported strided arrays...
Re:Variable Length Arrays are problematic
by geofft on Monday July 05, 2021 @11:37PM
(#27744013)
Right, but I think there's a valid question of why you need to ban strings entirely, and why you can't have variable-length allocations provided you use the heap instead of VLAs. (You can.)
Re:Variable Length Arrays are problematic
by foota on Tuesday July 06, 2021 @01:01AM
(#27744393)
Right, that's what I was saying. The statement "The kernel has limited stack space and isn't good at growing it." felt like a non sequitur when followed by "QNX got this right. No strings in the kernel. Everything is either fixed-length or in user space. A privileged program in user space deals with filenames and such." Whether or not you use fixed space is orthogonal to whether you use VLA.
Re:Variable Length Arrays are problematic
by geofft on Monday July 05, 2021 @11:35PM
(#27744005)
Most kernels do have a heap and they work fine for this purpose, as the article advocates. After all, they need a page allocator to respond to requests from userspace programs for dynamic allocation (unless it's an extremely embedded OS where memory is allocated to tasks at design / compile time - think Apollo Guidance Computer, not QNX). So they may as well allocate pages for their own use, if they want.
If you want string-handling on the heap, you probably also want some sort of a malloc implementation, so you can handle allocation requests that are less than one page, but that's just an algorithm that sits on top of the page allocator.
You don't want to overuse it, though. Page allocation can fail, and more interestingly, it can require blocking - maybe you're not out of memory, exactly, but you've got dirty buffers that need to be flushed to disk (or worse, to NFS). If you're handling a system call from a userspace program, blocking is probably fine. But the kernel runs in more contexts than that. One problem is that the code that handles flushing dirty buffers, and any code that it calls, cannot block; otherwise, you might deadlock, because you're trying to allocate a new page so you can finish free a page. (And in the case of NFS, that includes basically all of the socket code in the kernel.) You also don't want to block inside interrupt handlers, even if the thing the interrupt handler is doing is putting some data on a queue and letting a kernel thread pick it up. Those buffers need to be allocated in advance, or at least come from a special pool of ready-to-use pages that can always be allocated without blocking.
In a kernel that supports swap, you can choose to swap out basically anything to make more room, but that has its own deadlock problem too. Code used by any disk handler (and any filesystem, if you support swap files) cannot allocate memory that can be swapped out; otherwise you might not be able to swap that memory back in. One common approach, which Linux takes, is to say that memory allocated by the kernel simply cannot swap. But that means that you can't allocate too much inside the kernel. NT actually has a swappable kernel pool, and the infamous IRQL_NOT_LESS_OR_EQUAL blue screen means that a kernel driver tried to access data that was swapped out in a context where it wasn't allowed to swap.
Here's the Linux kernel's documentation on its various allocation options:
Re:Variable Length Arrays are problematic
by Animats on Tuesday July 06, 2021 @02:38AM
(#27744905)
Page allocation can fail, and more interestingly, it can require blocking
Yes. It used to be possible to crash the Linux kernel by doing lots of random I/O, as with a database, along with lots of sequential I/O, and running out of memory so that paging started. This would result in a need to get a page of memory for the kernel when a lock was set that prevented releasing an I/O buffering page. Haven't seen that in years, so I assume it got fixed.
Re:Variable Length Arrays are problematic
by omegalulw on Tuesday July 06, 2021 @12:48AM
(#27744318)
Why not simply let kernel memory allocators specify if their memory is safe to swap out? The file system can declare no and other modules can declare yes? From userland you don't allow setting yes.
Re:Variable Length Arrays are problematic
by lmilcin on Monday July 05, 2021 @07:57PM
(#27742957)
From my point of view VLA belongs to a class of features (along with, for example, setjump/longjump) that are best not mentioned to novice developers.
Standards aimed at security/reliability (for example MISRA) outright ban using these as they are just not worth the risk.
I have never actually needed VLAs in all the projects I did in ANSI C and I only once used alloca to provide a buffer on a stack for a serializer, but in that case the buffer size was configured at the start of the application and I could most likely just used a buffer provided by the application.
Re:Variable Length Arrays are problematic
by kbuck on Tuesday July 06, 2021 @02:29AM
(#27744856)
Something that bothered me: The author mentions that the worst case of VLA usage is an exploitable vulnerability, then goes on to call malloc with n * size, where n is controlled by the user. This should either be bounds checked or calloc should be used instead, since the "fix" presented may also introduce an exploitable vulnerability.
Re:Variable Length Arrays are problematic
by caf on Monday July 05, 2021 @08:20PM
(#27743090)
The last example is incorrect:
int foo(int (*array)[3]) { return (*array)[1]; } // VLA pointer
That is not a "VLA pointer" - there is no variably modified type here, that is just an ordinary pointer to array type, that worked perfectly fine as written back in your grandfather's C89.
Re:Variable Length Arrays are problematic
by zzo38computer on Monday July 05, 2021 @01:50AM
(#27734971)
I don't like VLA and don't use that feature of C. Due to its slowness and difficulty in the compiler, and because it doesn't seem useful compared with the other things in C, it is a feature that I would think they should not have included (there are some other such things too). There are good features added into C though, many of which are GNU extensions. Some of the newer things are also good, such as the proposal for a #embed command. There are other things I also think should be added into C, including "goto case", and more sophisticated preprocessor stuff. However, some of the stuff I disagree with (including even one thing from C from the first that I dislike, which is the confusing syntax for types).
Re:Variable Length Arrays are problematic
by binarybanana on Tuesday July 06, 2021 @08:37AM
(#27747628)
I don't get how there is a meaningful difference with regard to failure between a VLA on the stack and malloc'ing a buffer on the heap. In both cases you have to do a check if you want to avoid a crash on resource exhaustion. The only difference is that stack size is not standardized among implementaions, but IIRC you can get/set it appropriately for your needs with POSIX APIs (I think pthreads has such a function?). Even on Linux you can disable overcommit if you want to reliably handle OOM in user space and if you don't the malloc case is actually less reliable since it will never fail anyway.
Also I wonder how VLAs compare to alloca? It's basically malloc, but on the stack and I've seen a lot of software use it, for example nnn and picom make allocations with it. Wouldn't the same issues also affect alloca? I mean an array is just a contiguous memory buffer in C, so alloca could be used to back an array of variable size in the same way, or is there something I'm missing?
But then, neither is the size of RAM, or whatever limits are in place.
FLA is the one where the undefined size array is put at the end of a struct and you carefully access it beyond the size of the struct itself. Usually malloc as you would with a VLA.
1. I’m sure Rust people really hate this idea.
2. I’m just realizing you could be really reckless point a FLA to a VLA used as a buffer, maybe I’ll set that up next time I’m interviewing.
Re:Variable Length Arrays are problematic
by CodesInChaos on Tuesday July 06, 2021 @11:35AM
(#27749941)
> 1. I’m sure Rust people really hate this idea.
Rust has unsized types, like slices. Such types can't be passed by value and pointers to such types consist of two words (address and length for slices). You can put an unsized type at the end of a struct, resulting in an unsized struct. Using a slice as the last member is equivalent to a flexible array member in C.
Unfortunately they're barely usable in the current state, since there is no good way to construct such a struct.
Re:Variable Length Arrays are problematic
by SV_BubbleTime on Tuesday July 06, 2021 @12:41PM
(#27750926)
>You can put an unsized type at the end of a struct, resulting in an unsized struct. Using a slice as the last member is equivalent to a flexible array member in C.
News to me! I figured it was inherently a little "unsafe" and Rust's thing in mem safety. Good to know!
>Unfortunately they're barely usable in the current state, since there is no good way to construct such a struct.
Ok, well, now that's just bizarre, but I assume there is a good reason. I'll get on Rust when it's "official" somewhere for embedded. Until then, a strange and mystical shadow in the forest for me.
Re:Variable Length Arrays are problematic
by josefx on Tuesday July 06, 2021 @01:47AM
(#27744603)
> Well, the difference is in possibility of checking the value returned by malloc() and thus being able to, for example, inform the user about the error
Not on Linux. Memory over commit means that you get a pointer pointing to nowhere^1 . Your program will simply fail when it traverses the allocated address range the first time and the OS ends up unable to allocate enough memory pages to back the address range.
1 unless you exceed the total existing memory+swap space in a single allocation
QNX got this right. No strings in the kernel. Everything is either fixed-length or in user space. A privileged program in user space deals with filenames and such.
Do you have a source for that claim? The C11 standard notes that memory associated with a variable length array can be "squandered" by a longjmp, as far as I understand that shouldn't happen with stack allocation.
Most implementations may use stack allocation, leading to the stackoverflow problems described in the article. However as far as I can tell the standard doesn't require this.
In C89 the ability to pass multi-dimensional arrays to functions was not very useful, since the inner dimensions could not vary at runtime. Fixing this was the main point of the VLA feature, at least for people who work on array data. It would be even more useful, had they supported strided arrays...
If you want string-handling on the heap, you probably also want some sort of a malloc implementation, so you can handle allocation requests that are less than one page, but that's just an algorithm that sits on top of the page allocator.
You don't want to overuse it, though. Page allocation can fail, and more interestingly, it can require blocking - maybe you're not out of memory, exactly, but you've got dirty buffers that need to be flushed to disk (or worse, to NFS). If you're handling a system call from a userspace program, blocking is probably fine. But the kernel runs in more contexts than that. One problem is that the code that handles flushing dirty buffers, and any code that it calls, cannot block; otherwise, you might deadlock, because you're trying to allocate a new page so you can finish free a page. (And in the case of NFS, that includes basically all of the socket code in the kernel.) You also don't want to block inside interrupt handlers, even if the thing the interrupt handler is doing is putting some data on a queue and letting a kernel thread pick it up. Those buffers need to be allocated in advance, or at least come from a special pool of ready-to-use pages that can always be allocated without blocking.
In a kernel that supports swap, you can choose to swap out basically anything to make more room, but that has its own deadlock problem too. Code used by any disk handler (and any filesystem, if you support swap files) cannot allocate memory that can be swapped out; otherwise you might not be able to swap that memory back in. One common approach, which Linux takes, is to say that memory allocated by the kernel simply cannot swap. But that means that you can't allocate too much inside the kernel. NT actually has a swappable kernel pool, and the infamous IRQL_NOT_LESS_OR_EQUAL blue screen means that a kernel driver tried to access data that was swapped out in a context where it wasn't allowed to swap.
Here's the Linux kernel's documentation on its various allocation options:
https://www.kernel.org/doc/html/latest/core-api/memory-alloc...
https://www.kernel.org/doc/html/latest/core-api/mm-api.html#...
Yes. It used to be possible to crash the Linux kernel by doing lots of random I/O, as with a database, along with lots of sequential I/O, and running out of memory so that paging started. This would result in a need to get a page of memory for the kernel when a lock was set that prevented releasing an I/O buffering page. Haven't seen that in years, so I assume it got fixed.
Where they work just fine.
Standards aimed at security/reliability (for example MISRA) outright ban using these as they are just not worth the risk.
I have never actually needed VLAs in all the projects I did in ANSI C and I only once used alloca to provide a buffer on a stack for a serializer, but in that case the buffer size was configured at the start of the application and I could most likely just used a buffer provided by the application.
Also I wonder how VLAs compare to alloca? It's basically malloc, but on the stack and I've seen a lot of software use it, for example nnn and picom make allocations with it. Wouldn't the same issues also affect alloca? I mean an array is just a contiguous memory buffer in C, so alloca could be used to back an array of variable size in the same way, or is there something I'm missing?
But then, neither is the size of RAM, or whatever limits are in place.
But if I’m not… https://en.wikipedia.org/wiki/Flexible_array_member
FLA is the one where the undefined size array is put at the end of a struct and you carefully access it beyond the size of the struct itself. Usually malloc as you would with a VLA.
1. I’m sure Rust people really hate this idea.
2. I’m just realizing you could be really reckless point a FLA to a VLA used as a buffer, maybe I’ll set that up next time I’m interviewing.
Rust has unsized types, like slices. Such types can't be passed by value and pointers to such types consist of two words (address and length for slices). You can put an unsized type at the end of a struct, resulting in an unsized struct. Using a slice as the last member is equivalent to a flexible array member in C.
Unfortunately they're barely usable in the current state, since there is no good way to construct such a struct.
News to me! I figured it was inherently a little "unsafe" and Rust's thing in mem safety. Good to know!
>Unfortunately they're barely usable in the current state, since there is no good way to construct such a struct.
Ok, well, now that's just bizarre, but I assume there is a good reason. I'll get on Rust when it's "official" somewhere for embedded. Until then, a strange and mystical shadow in the forest for me.
Not on Linux. Memory over commit means that you get a pointer pointing to nowhere^1 . Your program will simply fail when it traverses the allocated address range the first time and the OS ends up unable to allocate enough memory pages to back the address range.
1 unless you exceed the total existing memory+swap space in a single allocation