The kernel radar: folios, multi-generational LRU, and Rust [LWN.net]

The kernel radar: folios, multi-generational LRU, and Rust

Posted Jan 21, 2022 12:30 UTC (Fri) by eru (subscriber, #2753)
Parent article: The kernel radar: folios, multi-generational LRU, and Rust

The Rust language wasn't built with the idea that code might need to continue when a memory allocation fails; instead, the normal result is an immediate crash.

A surprising feature in a language that has been touted as a C replacement for low-level programming. Of course, when you are out of memory, there typically are no good options, but a language for low-level programming must allow the programmer to decide what happens next.

The kernel radar: folios, multi-generational LRU, and Rust

Posted Jan 21, 2022 17:43 UTC (Fri) by walters (subscriber, #7396) [Link]

The article phrased this poorly. The Rust *language* is independent of the default standard library. Plenty of use cases (including Rust-for-Linux) use "no-std" which fully supports writing code with fallible allocations. Plenty more at e.g. https://doc.rust-lang.org/stable/embedded-book/intro/no-s...

The kernel radar: folios, multi-generational LRU, and Rust

Posted Jan 21, 2022 18:03 UTC (Fri) by atnot (guest, #124910) [Link]

It's not really accurate that the language wasn't built with the Idea in mind. Just like C, Rust does not depend on any kind of allocator, fallible or not. All of the difficulties here are just from the desire to reuse a userspace library (alloc) in the kernel. They certainly could have just written their own allocator api, list types, etc. just like the kernel does, but since the standard library developers were willing to support their use case it was just more convenient to share.

The kernel radar: folios, multi-generational LRU, and Rust

Posted Jan 23, 2022 3:01 UTC (Sun) by NYKevin (subscriber, #129325) [Link] (2 responses)

Well, let's compare to the (userspace) alternatives:

1. In a managed language, like Java, you get some sort of "out of memory" exception. Handling these exceptions safely is complicated and error-prone, and the official documentation will often encourage the programmer to just "let it crash" instead of trying to deal with the problem gracefully. In most cases, these languages will try to reclaim previously allocated memory with the garbage collector before throwing these exceptions.
2. In C++, std::bad_alloc is thrown, which is like the managed case except that stack unwinding will cause destructors to run (in the managed case, finalizers *might* run, but there is no guarantee of when they get called). If any of those destructors tries to allocate any memory, for any reason, it might cause a second std::bad_alloc to get thrown, and if a destructor throws an exception while another exception is already pending, the runtime gives up and calls std::terminate. Therefore, if you want to handle fallible allocations, every destructor in your entire program must be in on the joke.
3. In C, malloc returns a null pointer. If you forget to check for it, undefined behavior occurs (but in practice, you probably just segfault most of the time). If you remembered to check for it, you can handle it in whatever way you like, but in most cases you either return an error to your caller, or call longjmp(3) on a pre-allocated jmp_buf to go back to the main event loop or some other top-level scope that can reasonably figure out what to do next.
4. Regardless of language, it's possible for the OS to lie to you and give you memory which doesn't actually exist, then kill you when you try to use it. Linux actually does this,* and I believe it's common in other modern OSes as well. Where this functionality is enabled, any program can crash upon the system running out of memory, and there's nothing the programmer can reasonably do about it.

Sure, discount (1) all you like, but the practical reality is that running out of memory is really hard to handle safely when you're running in userspace, regardless of whether you're a high-level language or a low-level language.

* The OOM killer is more complicated than what I have described here.

The kernel radar: folios, multi-generational LRU, and Rust

Posted Jan 23, 2022 10:07 UTC (Sun) by farnz (subscriber, #17727) [Link]

As a side note, the Rust team are working on providing a decent API for fallible allocations. The raw Allocator trait that's going to be the interface between allocators and the rest of the language only has fallible functions that may allocate. The only function in that API that must succeed is free.

Then, there's effort ongoing to support fallible allocation in container APIs, with its own tracking issue.

There's a lot of effort going in to making this a supportable API for the long term; the key "odd" decision Rust seems to be making here is that instead of requiring every operation that could allocate to cope with the risk of allocation failure, there will be a mechanism (try_reserve on collections, for example) that guarantees that you can do a certain number of operations without allocating, and that mechanism can fail. It's then up to the users of the APIs to ensure that memory is either reserved up-front, or to take the risk of surprise allocation failure.

And this matches the underlying observation you've made; it's incredibly hard to handle allocation failure if it can happen at any time, and thus the entire application needs to either be bug-free in handling the rare error case (allocation failure), which in C++ means that everything has to meet the strong exception safety guarantee, or you need to confine allocation failures to a few places where you have hardened your code.

The kernel radar: folios, multi-generational LRU, and Rust

Posted Feb 6, 2022 3:02 UTC (Sun) by HelloWorld (guest, #56129) [Link]

> 2. In C++, std::bad_alloc is thrown, which is like the managed case except that stack unwinding will cause destructors to run (in the managed case, finalizers *might* run, but there is no guarantee of when they get called). If any of those destructors tries to allocate any memory, for any reason, it might cause a second std::bad_alloc to get thrown, and if a destructor throws an exception while another exception is already pending, the runtime gives up and calls std::terminate. Therefore, if you want to handle fallible allocations, every destructor in your entire program must be in on the joke.

Well, most destructors don't require allocation but do free up some memory. This means that when a bad_alloc is thrown, there's a pretty good chance that by the time you reach a destructor that allocates, some memory has already been freed by a destructor that ran before, and so your allocation may very well succeed. There are cases where it's better to try to recover from an allocation failure and sometimes fail than to not try at all.

Also, you might be able to allocate whatever memory you need to run the destructor in the constructor, thus avoiding the need to allocate in the destructor.

The kernel radar: folios, multi-generational LRU, and Rust

Posted Mar 3, 2022 18:19 UTC (Thu) by jd (guest, #26381) [Link]

There are a variety of approaches to out-of-memory issues in different languages, and there has been quite an interesting on-and-off debate in computing about fault-intolerant languages (which can be useful because a program isn't trying to limp on with an uncertain state).

In a microkernel, where you might very well want a module to crash cleanly and get restarted, a fault-intolerant language would seem to make a lot of sense. Rust might well be ideal for writing modules in the L4 world. I'm not sure how it makes sense in Linux, although if the primary kernel developers say it does then there's an excellent chance it does even if I can't see it.

There are other languages that might have value (or even more value) in the kernel, but they're either hopelessly obscure or too difficult to find a 64-bit compiler for, and I seriously doubt there would be interest in yet another language until Rust succeeds/fails, the reasons are known and there are people who might credibly actually use such a provision.