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

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

Posted Jan 20, 2022 22:49 UTC (Thu) by developer122 (guest, #152928)
Parent article: The kernel radar: folios, multi-generational LRU, and Rust

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.

to post comments

Rust

Posted Jan 20, 2022 23:29 UTC (Thu) by tialaramex (subscriber, #21167) [Link] (7 responses)

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.

Rust

Posted Jan 20, 2022 23:43 UTC (Thu) by ejr (subscriber, #51652) [Link] (2 responses)

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

Posted Jan 21, 2022 0:57 UTC (Fri) by tialaramex (subscriber, #21167) [Link] (1 responses)

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

Posted Jan 21, 2022 14:21 UTC (Fri) by ejr (subscriber, #51652) [Link]

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.

Rust

Posted Jan 21, 2022 19:25 UTC (Fri) by ballombe (subscriber, #9523) [Link] (1 responses)

Is there an usable subset of rust without object metadata ?

Rust

Posted Jan 26, 2022 18:37 UTC (Wed) by iq-0 (subscriber, #36655) [Link]

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.

Rust

Posted Jan 22, 2022 1:02 UTC (Sat) by plugwash (subscriber, #29694) [Link] (1 responses)

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

Rust

Posted Jan 22, 2022 21:32 UTC (Sat) by tialaramex (subscriber, #21167) [Link]

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.

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

Posted Jan 21, 2022 3:07 UTC (Fri) by willy (subscriber, #9762) [Link] (10 responses)

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.

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

Posted Jan 21, 2022 4:40 UTC (Fri) by Cyberax (✭ supporter ✭, #52523) [Link]

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

Posted Jan 21, 2022 9:00 UTC (Fri) by ldearquer (guest, #137451) [Link] (8 responses)

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

Posted Jan 21, 2022 12:11 UTC (Fri) by pbonzini (subscriber, #60935) [Link] (7 responses)

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

Posted Jan 21, 2022 12:36 UTC (Fri) by ldearquer (guest, #137451) [Link] (6 responses)

I see, thanks for clarifying :)

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

Posted Jan 21, 2022 12:45 UTC (Fri) by pbonzini (subscriber, #60935) [Link] (5 responses)

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

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

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

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

Posted Jan 21, 2022 18:10 UTC (Fri) by pbonzini (subscriber, #60935) [Link] (3 responses)

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

Posted Jan 21, 2022 20:45 UTC (Fri) by atnot (guest, #124910) [Link] (2 responses)

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.

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

Posted Jan 25, 2022 4:15 UTC (Tue) by artem (subscriber, #51262) [Link] (1 responses)

> 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

Posted Jan 25, 2022 9:42 UTC (Tue) by atnot (guest, #124910) [Link]

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.