3 ms·

Can't use the standard library in the kernel, though. That's why there's special implementations of a lot of things you take for granted in kernel source, thing

Can't use the standard library in the kernel, though. That's why there's special implementations of a lot of things you take for granted in kernel source, things like "print".

floxy 3y ago
Seems like we are due for the cyclic interest in microkernels. I wonder what's the latest research on that front.
tczMUFlmoNk 3y ago
Rust's `sort_unstable` is available in `core` and does not require the standard library or the `alloc` crate, so, if my understanding is correct, even `no_std` programs like the kernel could use it? https://doc.rust-lang.org/core/primitive.slice.html#method.sort_unstable https://doc.rust-lang.org/core/primitive.slice.html#method.s... (It's interesting that the stable `sort`, by contrast, is only available in `std` because it uses an allocating timsort-variant.)
- steveklabnik 3y ago
  So you're not wrong, but also, the Linux kernel uses a modified variant of alloc, so not only can it use sort_unstable, it also has access to sort https://github.com/torvalds/linux/blob/2d1bcbc6cd703e64caf8df314e3669b4786e008a/rust/alloc/slice.rs#L274 https://github.com/torvalds/linux/blob/2d1bcbc6cd703e64caf8d...
- tialaramex 3y ago
  Most relevant element of what's going on here is that Rust's standard library is deliberately split three ways: Core has stuff that should "just work" on your target platform, Alloc adds stuff that further requires a Memory Allocator, which is something target hardware doesn't come with, but any non-trivial system is likely to build, then Std adds stuff which requires an Operating System, such as Files, and Threading C is technically also split, so called "freestanding" C implementations don't provide features like stdio but they do have e.g. math functions. C++ attempts something similar but it's a bit hit-and-miss as a truly "free standing" C++ doesn't entirely make sense, as systems that try to use C++ for very low level work often discover. The next less relevant observation is that Rust chooses to call these sort and sort_unstable - the one that's guaranteed to be available doesn't get the easier name, that's reserved for the one that definitely doesn't have unexpected behaviour. If you don't know what an "unstable" sort is, then sort_unstable's behaviour might in some cases be astonishing. Some languages make the opposite choice, which means programmers may use sort, not realising it's actually an unstable sort because the entire concept was never explained to them. This is one of many examples of Rust's safety achieved not via some sophisticated technology but just by thinking about why people screw up. Every Rust programmer who without thinking writes sort gets a stable sort, if that was too slow, they can choose sort_unstable, but doing so prompts them to consider, wait, is an unstable sort correct here? Finally the least relevant but hopefully still interesting observation is that it is quite possible to have a stable sort which doesn't require allocation, but the performance is not so hot. It seems pretty unlikely that you must have a stable sort and you can't afford an allocator and yet you don't mind the performance hit. As I understand it though some C++ libraries do offer this.
erk__ 3y ago
As PHK points out [0] qsort was imported [1] into the kernel in 1995, it was simply never used for the boot process, but it is availible. [0]: https://twitter.com/bsdphk/status/1659568675899228163 https://twitter.com/bsdphk/status/1659568675899228163 [1]: https://github.com/freebsd/freebsd-src/commit/d89a1b600fc07174b854f76aaddffe475e65ef36#diff-5d3389cd135876e0a2f899d06b38c59d40d8736ed57eae6989bad02fb92263c3 https://github.com/freebsd/freebsd-src/commit/d89a1b600fc071...
- canucker2016 3y ago
  Looks like the code to bubble-sort the SYSINIT objects was committed a few months BEFORE this kernel qsort code was committed (late Aug 1995 vs early Nov 1995). So that's why the sort-SYSINIT objects code didn't use qsort. I'd also guess that there were fewer SYSINIT objects to sort back in 1995 than today. see ~line 150 of sys/kern/init_main.c in https://github.com/freebsd/freebsd-src/commit/2b14f991e64ebe31ca31a1a41237061c22a753d0#diff-892b418520675d603d352b09af1db41d918281f57aa0042b4d76d7a94fb8d2d1 https://github.com/freebsd/freebsd-src/commit/2b14f991e64ebe...

Can't use the standard library in the kernel, though. That's why there's special implementations of a lot of things you take for granted in kernel source, things like "print".

floxy 3y ago

Seems like we are due for the cyclic interest in microkernels. I wonder what's the latest research on that front.

tczMUFlmoNk 3y ago

Rust's `sort_unstable` is available in `core` and does not require the standard library or the `alloc` crate, so, if my understanding is correct, even `no_std` programs like the kernel could use it? https://doc.rust-lang.org/core/primitive.slice.html#method.sort_unstable https://doc.rust-lang.org/core/primitive.slice.html#method.s... (It's interesting that the stable `sort`, by contrast, is only available in `std` because it uses an allocating timsort-variant.)

steveklabnik 3y ago
So you're not wrong, but also, the Linux kernel uses a modified variant of alloc, so not only can it use sort_unstable, it also has access to sort https://github.com/torvalds/linux/blob/2d1bcbc6cd703e64caf8df314e3669b4786e008a/rust/alloc/slice.rs#L274 https://github.com/torvalds/linux/blob/2d1bcbc6cd703e64caf8d...
tialaramex 3y ago
Most relevant element of what's going on here is that Rust's standard library is deliberately split three ways: Core has stuff that should "just work" on your target platform, Alloc adds stuff that further requires a Memory Allocator, which is something target hardware doesn't come with, but any non-trivial system is likely to build, then Std adds stuff which requires an Operating System, such as Files, and Threading C is technically also split, so called "freestanding" C implementations don't provide features like stdio but they do have e.g. math functions. C++ attempts something similar but it's a bit hit-and-miss as a truly "free standing" C++ doesn't entirely make sense, as systems that try to use C++ for very low level work often discover. The next less relevant observation is that Rust chooses to call these sort and sort_unstable - the one that's guaranteed to be available doesn't get the easier name, that's reserved for the one that definitely doesn't have unexpected behaviour. If you don't know what an "unstable" sort is, then sort_unstable's behaviour might in some cases be astonishing. Some languages make the opposite choice, which means programmers may use sort, not realising it's actually an unstable sort because the entire concept was never explained to them. This is one of many examples of Rust's safety achieved not via some sophisticated technology but just by thinking about why people screw up. Every Rust programmer who without thinking writes sort gets a stable sort, if that was too slow, they can choose sort_unstable, but doing so prompts them to consider, wait, is an unstable sort correct here? Finally the least relevant but hopefully still interesting observation is that it is quite possible to have a stable sort which doesn't require allocation, but the performance is not so hot. It seems pretty unlikely that you must have a stable sort and you can't afford an allocator and yet you don't mind the performance hit. As I understand it though some C++ libraries do offer this.

erk__ 3y ago

As PHK points out [0] qsort was imported [1] into the kernel in 1995, it was simply never used for the boot process, but it is availible. [0]: https://twitter.com/bsdphk/status/1659568675899228163 https://twitter.com/bsdphk/status/1659568675899228163 [1]: https://github.com/freebsd/freebsd-src/commit/d89a1b600fc07174b854f76aaddffe475e65ef36#diff-5d3389cd135876e0a2f899d06b38c59d40d8736ed57eae6989bad02fb92263c3 https://github.com/freebsd/freebsd-src/commit/d89a1b600fc071...

canucker2016 3y ago
Looks like the code to bubble-sort the SYSINIT objects was committed a few months BEFORE this kernel qsort code was committed (late Aug 1995 vs early Nov 1995). So that's why the sort-SYSINIT objects code didn't use qsort. I'd also guess that there were fewer SYSINIT objects to sort back in 1995 than today. see ~line 150 of sys/kern/init_main.c in https://github.com/freebsd/freebsd-src/commit/2b14f991e64ebe31ca31a1a41237061c22a753d0#diff-892b418520675d603d352b09af1db41d918281f57aa0042b4d76d7a94fb8d2d1 https://github.com/freebsd/freebsd-src/commit/2b14f991e64ebe...