LWN: Comments on "The kernel radar: folios, multi-generational LRU, and Rust"

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

jd — Thu, 03 Mar 2022 18:19:41 +0000

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.

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

HelloWorld — Sun, 06 Feb 2022 03:02:18 +0000

> 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.

Rust

iq-0 — Wed, 26 Jan 2022 18:37:18 +0000

What do you mean with object metadata? Rust doesn't have RTTI if that's what you mean. Aside from DWARF information it only has vtables for trait objects that are used in the code (bare minimum, those things are basically structs with function pointers like one would use in C for this same problem). If you're referring to the name mangling (the loooong type signatures) those have more to do with the way Rust solves diamond dependency conflicts and the liberal usage of templated types.

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

atnot — Tue, 25 Jan 2022 09:42:04 +0000

Oh, I hadn't considered that you could mutate a lists through another one...

I don't immediately see any reason why it shouldn't be possible. Rust's weak references have similar semantics albeit still require reference counting because it can't just go and remove the remaining references like with a list. I don't think it's natively supported by the intrusive-collections crate mentioned above though. But you should be able to express it with a safe interface.

Evidently there doesn't seem to be a lot of demand for something like that from existing rust users though. intrusive-collections is already not exactly widely used. I've personally never found a reason to use it despite looking for excuses, there's just too many specialized high quality data structure libraries to justify it. Maybe some day.

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

artem — Tue, 25 Jan 2022 04:15:06 +0000

> Once you put things into multiple collections you need some way of knowing whether you should free items when removing them.

> If you don't know whether it's the last reference, you need some kind of reference count

With multiple intrusive lists, you can declare some of them owning and some of them non-owning.

When a thing is not on any of the owning lists, it's removed from the rest and dropped.

No reference counting necessary.

How would one do that in Rust?

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

farnz — Sun, 23 Jan 2022 10:07:17 +0000

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

NYKevin — Sun, 23 Jan 2022 03:01:52 +0000

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.

Rust

tialaramex — Sat, 22 Jan 2022 21:32:42 +0000

What I'm getting at is that your fork can literally rip out the code that does floating point math. Rust's actual standard library won't do that, but it will probably some day take that cfg() parameter to turn off floating point math or agree some other way forward. Meanwhile Rust for Linux gets a library it can ship in Linux.

It's future proofed in that the assumption is some day Rust will have a way to disable or sidestep this, and at that point Rust for Linux can just ship the normal core library (in this respect).

The fact Rust's standard library relies on Rust's nightly features is orthogonal, this configuration parameter isn't relying on yet-to-stabilise feature, it's just that the code in core wants to do floating point maths, and Linux doesn't want that to be a possibility. In that specific case just ripping out the offending code is an effective solution, you could do it once for each Linux release and while somewhat tiresome it's not unmanageable.

Rust

plugwash — Sat, 22 Jan 2022 01:02:16 +0000

"However, ultimately you _could_ do this surgery by hand and in effect "fork" the core library, especially if you knew a real fix was coming later."

The rust standard library uses and will probably always use features that will not be part of stable rust. So forking the standard library doesn't really help you with future-proofing your code.

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

atnot — Fri, 21 Jan 2022 20:45:01 +0000

I'm not sure that's really much less ergonomic than C? You still have the same issue there. Once you put things into multiple collections you need some way of knowing whether you should free items when removing them. That's true regardless of whether the compiler notices it.

If you don't know whether it's the last reference, you need some kind of reference count and if you do you'll need to prove it, either to yourself or preferably some program. It's not much different.

Rust

ballombe — Fri, 21 Jan 2022 19:25:29 +0000

Is there an usable subset of rust without object metadata ?

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

pbonzini — Fri, 21 Jan 2022 18:10:57 +0000

Sure, I only said it doesn't support them "very well". If you check https://docs.rs/intrusive-collections/0.9.3/intrusive_col..., having the same object in many lists (which is a major advantage of intrusive collections) requires reference counting.

This is enough of a disadvantage that the same crate includes an unsafe primitive to avoid this (https://docs.rs/intrusive-collections/0.9.3/intrusive_col...).

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

atnot — Fri, 21 Jan 2022 18:03:47 +0000

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

walters — Fri, 21 Jan 2022 17:43:55 +0000

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

walters — Fri, 21 Jan 2022 17:41:02 +0000

There is https://crates.io/crates/intrusive-collections for example.

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

ejr — Fri, 21 Jan 2022 14:22:31 +0000

Modula-3 tried really, really hard to come up with generalizable semantics to apply when allocation fails. I don't believe they ever did.

Rust

ejr — Fri, 21 Jan 2022 14:21:09 +0000

Ah, I thought GAT was a misspelling of GADT. And traits sound more like type classes... So essentially this is another version of ML module signatures / Haskell type classes. I'm guessing it looks more friendly to folks coming from C/C++.

Stability is pre-standardization like C/C++ attributes, or would be if there were multiple compilers out there. (gcc was on its way at some point, right?) Many mostly-single-vendor languages have stable v. implementation gizmos. At least this term is fairly well shared.

Rust isn't useful in my daily life (heavily shared memory structures being changed rapidly), so I haven't really poked at it.

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

pbonzini — Fri, 21 Jan 2022 12:45:37 +0000

I'll add that Rust in general does not support intrusive data structures very well, because it is not very much friend with data that can be reached in different ways. You would have to wrap it with a reference count (Rc or Arc) and with either run-time borrow checking or a mutex (respectively RefCell and Mutex).

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

ldearquer — Fri, 21 Jan 2022 12:36:21 +0000

I see, thanks for clarifying :)

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

eru — Fri, 21 Jan 2022 12:30:35 +0000

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

pbonzini — Fri, 21 Jan 2022 12:11:14 +0000

Usually Linux uses intrusive linked lists. They allow the same node to be part of multiple data structures, so you find the node in a different data structure (for example an array or hash table) and juggle the pointers in the node to move it to the end of the LRU list.

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

ldearquer — Fri, 21 Jan 2022 09:00:28 +0000

For the linked list, wouldn't it require O(n) finding the node? Then place it on the highest index O(1)? So you would have O(n) (+ O(1)) vs 2·O(log n)

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

Cyberax — Fri, 21 Jan 2022 04:40:02 +0000

You can use heaps, not full B-trees. That actually would be interesting to measure, it's quite possible that not having to chase the pointers might speed them up.

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

willy — Fri, 21 Jan 2022 03:07:10 +0000

Ok, I'll bite ... How do you efficiently implement an LRU with a B-tree? Every time you access an element (let's say an inode) in the inode cache, you remove it from wherever it currently is in the B-tree and move it to the highest unused index. That's two O(log n) operations, versus a linked list, which is two O(1) operations.

Rust

tialaramex — Fri, 21 Jan 2022 00:57:43 +0000

I am happy within reason to define terms, and it's likely others could help too, but of course I need to know what you didn't understand.

For example maybe with ML in your background Generic Associated Types are obvious, or maybe not, with GATs Rust can express the idea that some trait can have associated types which are generic. So e.g. today an Iterator has an associated type saying which Item type it iterates over, but that associated type has to be specific, like this is an Iterator over Strings, there are some traits people would like to write where you'd want to express that the associated type has some generic properties but not tie down the specifics. Evidently the Rust for Linux have some use for this feature.

But equally maybe you don't know what Rust's traits are. Traits are similar to the "interfaces" feature in many object oriented languages, in that they express some capability or property common to multiple types. A trait must be explicitly implemented for any particular type, either with the definition of the type itself, or with the definition of the trait, and each such implementation stands alone. So you can be sure that if SomeTrait is implemented for ThisThing, either the author of ThisThing intended that, or the author of SomeTrait or perhaps both, as a result traits have Semantics - there is no risk of their being a mere accident of syntax as with say C++ Concepts.

Maybe you know about Rust stability, or maybe not, in Rust there's a concept of "unstable" features. These features exist, and they work in whatever build of Rust you have, but tomorrow there might be a new Rust version and they're altered, or renamed, or gone. In contrast all the stable features of Rust are promised to still work into the indefinite future, none have been removed since 1.0 in 2015. You have to specifically opt in to having unstable features, and to each specific unstable feature you want. Today Rust for Linux needs several such features. Internally Rust uses some unstable features, but without opting in you can't and probably most people shouldn't, thus it is desirable for Rust for Linux to rely as much as possible on stable features only.

Rust

ejr — Thu, 20 Jan 2022 23:43:36 +0000

I am trying to parse both your message as well as the one to which you are responding.

And I'm a FORTRAN (yes, all caps, including WATFIV) / APL / C person. With a background in more formal language systems like ML.

Please define your terminology, It appears as if yet another terminology is a major hurdle for acceptance.

Rust

tialaramex — Thu, 20 Jan 2022 23:29:49 +0000

The stability list isn't TOO bad once you consider it standing back a few paces.

I count 17 items, 4 are cfg() parameters, to switch off features from the allocator and, in one case, the core Rust library†. That latter is worth a moment's thought: Rust says you can format floating point numbers. Linux, of course, would very much rather you didn't use floating point numbers at all. So, Rust-for-Linux wants to tell the core library that we aren't going to be formatting any floating point numbers, blow up code that tries to do that, that's not valid Linux code. However, ultimately you _could_ do this surgery by hand and in effect "fork" the core library, especially if you knew a real fix was coming later.

2 more are -Z compiler flags. Rust's compiler has flags marked as not being stable with a Z prefix. It's not as though the kernel has never taken a dependency on compiler specific flags before, but clearly having a stable flag is better because it's a social contract not to move this particular feature unexpectedly.

Some of the others have community momentum behind them because they're things most Rust users want, GATs and more const are in that category. If Rust for Linux didn't engage with the main Rust community at all for 12 months, those things have traction and will make progress anyway. On the other hand, there are few applications outside the kernel for some of the compiler internals stabilization that Rust for Linux wants, if they never did this I for example, writing userspace code, would never ever notice.

It overall certainly means I don't expect to be running a Linux kernel with Rust in it in 2022 on my PC. But it also doesn't feel insurmountable, I could imagine reading an LWN piece before the end of the year about the "one big piece" missing, I just can't guess which piece that will be.

† Rust has a core library, which is at the heart of the standard library but must exist anyway. A few things in here are literally mandatory to Rust, e.g. the Drop trait must exist, it needn't be called Drop, but if there isn't one that's not Rust any more, the i32 type must exist, I don't even think you're allowed to call it something else, just too bad you must implement 32-bit signed integers - however a whole lot more are just useful, and not actually needed by Rust itself even if ordinary developers would be sad not to have them.

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

developer122 — Thu, 20 Jan 2022 22:49:28 +0000

Yeah, as I've heard Brian Cantrill say during a twitter space podcast thing, Rust and it's compiletime ownership-checks really doesn't work well with the concept of linked lists. After all "if you have b-trees, why would you use anything else?" And Rust's ownership checking makes (generically implemented) b-trees easy where as in C or other languages they tend to end up being a horrible buggy mess.