3 ms·

Does the kernel not have a heap?

by foota 5y ago

saurik 5y ago
A VLA is by definition on the stack; if you allocate memory in the heap you wouldn't need this feature in the first place.
- geofft 5y ago
  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.)
  - foota 5y ago
    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.
- josefx 5y ago
  > 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.
  - unnah 5y ago
    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...
  - saurik 5y ago
    Huh. I've now read the maybe-original article on this subject from 1994-- http://www.open-std.org/jtc1/sc22/wg14/www/docs/n317.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n317.pdf --and have also re-read this conversation thread, and yeah: I agree.
geofft 5y ago
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: https://www.kernel.org/doc/html/latest/core-api/memory-allocation.html https://www.kernel.org/doc/html/latest/core-api/memory-alloc... https://www.kernel.org/doc/html/latest/core-api/mm-api.html#watermark-modifiers-controls-access-to-emergency-reserves https://www.kernel.org/doc/html/latest/core-api/mm-api.html#...
- 5y ago

Does the kernel not have a heap?

by foota 5y ago

Does the kernel not have a heap?

A VLA is by definition on the stack; if you allocate memory in the heap you wouldn't need this feature in the first place.

geofft 5y ago
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.)
- foota 5y ago
  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.
josefx 5y ago
> 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.
- unnah 5y ago
  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...
- saurik 5y ago
  Huh. I've now read the maybe-original article on this subject from 1994-- http://www.open-std.org/jtc1/sc22/wg14/www/docs/n317.pdf http://www.open-std.org/jtc1/sc22/wg14/www/docs/n317.pdf --and have also re-read this conversation thread, and yeah: I agree.

geofft 5y ago

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: https://www.kernel.org/doc/html/latest/core-api/memory-allocation.html https://www.kernel.org/doc/html/latest/core-api/memory-alloc... https://www.kernel.org/doc/html/latest/core-api/mm-api.html#watermark-modifiers-controls-access-to-emergency-reserves https://www.kernel.org/doc/html/latest/core-api/mm-api.html#...

5y ago