A Rust implementation of Android's Binder

Posted Dec 2, 2023 9:45 UTC (Sat) by tialaramex (subscriber, #21167)
In reply to: A Rust implementation of Android's Binder by ballombe
Parent article: A Rust implementation of Android's Binder

Hmm. Where do you see an analogue of [T].select_nth_unstable_by ? My inexpert searching didn't find anything like this.

A Rust implementation of Android's Binder

Posted Dec 7, 2023 0:45 UTC (Thu) by wahern (subscriber, #37304) [Link] (1 responses)

Rust has a surfeit of library support for operating on array-based structures as lists and trees are quite cumbersome. But kernel data structures, when they need something sorted, are more likely to keep them in a sorted state, e.g. a sorted tree. Among other reasons, this approach provides consistent latency, as well as better avoids accidental performance issues. Until recently select_nth_unstable itself was accidentally quadratic, apparently: https://github.com/rust-lang/rust/issues/102451. But an interface like select_nth_unstable is a simple loop away from accidental quadratic behavior, anyhow.

This basic pattern is true of many niches where C remains common. The absence of language environment support for many of these algorithms is not felt as keenly as it would be were they missing from other languages such as Rust. Much of the work of a kernel is fundamentally about juggling shared, global resources, which necessarily involve gnarly reference graphs to which a language like Rust is fundamentally hostile, the design of which is largely predicated on pass-by-value and tidy ownership rules which track the call stack. Many kernel modules would be better off written in Rust, but also would ideally not run in kernel space at all.

A Rust implementation of Android's Binder

Posted Dec 9, 2023 19:15 UTC (Sat) by tialaramex (subscriber, #21167) [Link]

Accidentally quadratic _worst case_ only. It's the Quick Select defect, essentially a defect in the core of Quick Sort which for the same reason impacts most C qsort implementations into the 1990s and made some C++ standard library implementations non-compliant (the ISO document eventually promised better performance for its unstable sort than is actually achievable with Quick Sort) long after that.

I was skimming an old (like 30+ years old) Fortran book last week which gives this problem as a reason why its authors don't like Quick Sort although they admit it's technically faster on average. Today of course that book's advice is obsolete, you should use (and later Rust's authors did here) an introsort or some other modern better sort which didn't exist when that Fortran book was written

Keeping everything in order is excellent except when that's the wrong order, hence select_nth_unstable_by takes a function for the ordering we want, which doesn't have to be (indeed usually won't be) the natural ordering of this type. The kernel does have a lot of gnarly intrusive linked lists, and for its purpose this really is sometimes, even often the Right Thing™ because it's doing tricky concurrency acrobatics for example - but since linked lists are also the go-to data structure for C programmers that's not a sure bet as to why there's a linked list, sometimes it just "Not bad enough to pick something else" and a Vec<T> or similar structure natural to a Rust programmer might be better.