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

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

Posted Jan 21, 2022 3:07 UTC (Fri) by willy (subscriber, #9762)
In reply to: The kernel radar: folios, multi-generational LRU, and Rust by developer122
Parent article: The kernel radar: folios, multi-generational LRU, and Rust

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