experiment with relaxing the orphan rule

[y86-dev]

In Rust-for-Linux, we wish to split our single kernel crate into many smaller crates. There are various reasons for this:

• the ability to individually turn some crates off when they are not needed (for example in configurations that don't build drivers depending on that crate)
• splitting the code out of the rust/ directory and into their respective subsystems. Then every subsystem should have their own crate(s).
• refactoring core APIs into their own crate in order to publish them to crates.io

While I was splitting off the pin-init crate from the kernel crate in order to keep it in sync with the user-space version, I ran into a problem with the orphan rule. We also had previously anticipated that issues with the orphan rule would pop up if we were to split our kernel crate. The issue that I am facing currently is not that bad, as I can solve it with an additional trait. But in the long run, it won't be feasible to always create a workaround for orphan rule conflicts.
Note that in the kernel crate, we don't need to be protected by the orphan rule, as all ¹ dependents (and dependencies except core) of the kernel crate are under our control directly in-tree. So we would like to have some way to relax the orphan rule for our kernel crates.

Here is the error that I am currently running into.

I have this trait in pin-init (or the kernel crate before splitting):

/// Marker trait for types that can be initialized by writing just zeroes.
///
/// # Safety
///
/// The bit pattern consisting of only zeroes is a valid bit pattern for this type. In other words,
/// this is not UB:
///
/// ```rust,ignore
/// let val: Self = unsafe { core::mem::zeroed() };
/// ```
pub unsafe trait Zeroable {}

And an impl in the kernel crate for our own Box type:

// SAFETY: All zeros is equivalent to `None` (option layout optimization guarantee).
//
// In this case we are allowed to use `T: ?Sized`, since all zeros is the `None` variant and there
// is no problem with a VTABLE pointer being null.
unsafe impl<T: ?Sized, A: Allocator> Zeroable for Option<Box<T, A>> {}

The error that I get is expected, as neither Zeroable nor Option<T> are declared by the kernel crate:

error[E0117]: only traits defined in the current crate can be implemented for types defined outside of the crate
   --> rust/kernel/alloc/kbox.rs:107:1
    |
107 | unsafe impl<T: ?Sized, A: Allocator> Zeroable for Option<Box<T, A>> {}
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^-----------------
    | |                                                 |
    | |                                                 `Option` is not defined in the current crate
    | impl doesn't use only types from inside the current crate
    |
    = note: define and implement a trait or new type instead

error: aborting due to 1 previous error

In the latest RfL sync meeting, I brought this up and @ojeda had a good way of highlighting the problem: it's a chicken-and-egg situation, until we can relax the orphan rule, we're not able to split our crate due to these errors. And in order to know how the orphan rule should be relaxed, we have to split our crate. For this reason, it was suggested in the latest RfL sync meeting to use the following approach: introduce a nightly flag that disables the orphan rule wholesale (edit: for binary crates) and add a lint that warns on the orphan rule being violated. This way, we can split the kernel crate and see what types of orphan rule violations we would like to use without actually stabilizing anything. Miguel also added that you do not even need to ship it into nightly, you can just give us a modified compiler repository and we can test locally with that.

So essentially, this issue is for getting the ball rolling and having some nightly-only/custom-compiler-only flag to disable the orphan rule and see what types of violations we would like to have relaxed. Figuring out a stabilizable solution should come later, when we have an overview over all of the different kinds of relaxations we would like to have.

There also has been a zulip discussion about this topic.

cc @rust-lang/lang

Footnotes

1. while there are out-of-tree modules, they are always built for a pinned kernel version. When updating, they face the same issue on the C side, so it's OK to break them. ↩

[y86-dev]

@rustbot label +I-lang-nominated +I-types-nominated +A-rust-for-linux

[workingjubilee]

Note that the Linux kernel would, if it shipped anything with this variant of the compiler, lock us into supporting this code for its LTS lifecycle, no matter how unsound it was. This problem has already occurred with other flags that were proposed for addition "until a better solution was found".

Thus this proposed plan, and especially "just provide a modified compiler repo", is in conflict with our proposed project goal for stabilizing tooling for the kernel. A project I support, because then the kernel has less special asks "just for them" in our repository and inflicts less additional maintenance burdens.

[workingjubilee]

and this was without needing to worrying about language issues, including an upstream language community which refuses to make any kind of backwards compatibility guarantees, and which is actively hostile to a second Rust compiler implementation (I suspect because it might limit their ability to make arbitrary backwards-incompatble language changes).

This is the reputation we are getting in the kernel because Ted Ts'o thinks it's okay to bag on us because R4L uses unstable features. And this would be the most unstable of them all, because the flag would be inherently unsound, in this proposed form. I do not think it is a good idea to embark on a project to deliberately increase the amount of libelous accusations directed at our community.

[y86-dev]

Note that the Linux kernel would, if it shipped anything with this variant of the compiler, lock us into supporting this code for its LTS lifecycle, no matter how unsound it was. This problem has already occurred with other flags that were proposed for addition "until a better solution was found".

The nightly compiler flag will not be used in the kernel. It is only to experiment and find a path forward.

So essentially, we want a way to eventually have this feature in stable and only then use it in the kernel.

[bjorn3]

So essentially, this issue is for getting the ball rolling and having some nightly-only/custom-compiler-only flag to disable the orphan rule and see what types of violations we would like to have relaxed.

It shouldn't be too hard to patch rustc yourself to disable the orphan checker. Probably just a matter of adding return; at the top of the right function. I don't think we want to add an easy flag to disable it though. Neither an unstable cli flag nor a flag set when building rustc itself.

[y86-dev]

I sadly do not have the bandwidth to hack on the rust compiler. We also need to go through the proper procedure on the Rust side to get it implemented, so I brought this topic up in the RfL sync meeting. TC suggested that I create this issue and so I did.

[bjorn3]

I think the right location to add return Ok(()); is before

rust/compiler/rustc_hir_analysis/src/coherence/orphan.rs

Line 26 in c241e14

let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().instantiate_identity();

[oli-obk]

We also need to go through the proper procedure on the Rust side to get it implemented,

Why do you need proper procedures for an experiment?

Miguel also added that you do not even need to ship it into nightly, you can just give us a modified compiler repository and we can test locally with that.

Also as seen in bjorn's comment, if you want to do an experiment, people are usually happy to provide a patch under the condition it will never make it into the rustc repo itself.

Thus I don't quite understand why this issue exists.

[y86-dev]

I think the right location to add return Ok(()); is before

rust/compiler/rustc_hir_analysis/src/coherence/orphan.rs

Line 26 in c241e14
let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap().instantiate_identity();

Thanks for the pointer (I have only hacked twice on the rust compiler and I wouldn't even have had an idea of where to start), I will try it out next week.

We also need to go through the proper procedure on the Rust side to get it implemented,

Why do you need proper procedures for an experiment?

Miguel also added that you do not even need to ship it into nightly, you can just give us a modified compiler repository and we can test locally with that.

Also as seen in bjorn's comment, if you want to do an experiment, people are usually happy to provide a patch under the condition it will never make it into the rustc repo itself.

Thus I don't quite understand why this issue exists.

All I did was bring this up again in the RfL sync meeting and we talked a bit about how we could start an experiment to find a solution. We've talked about this before (as you can see in the zulip topic). As I wrote above, TC suggested that I create an issue for this.

[ojeda]

Note that the Linux kernel would, if it shipped anything with this variant of the compiler,

What was discussed in the meeting was explicitly about a flag (or fork, or experiment) that would never be used in upstream Linux, as @y86-dev explained.

Thus this proposed plan, and especially "just provide a modified compiler repo", is in conflict with our proposed project goal for stabilizing tooling for the kernel. A project I support, because then the kernel has less special asks "just for them" in our repository and inflicts less additional maintenance burdens.

I made the suggestion of providing the flag outside the usual compiler binaries precisely in case it helped Rust ensure this would never be used in upstream Linux.

This is the reputation we are getting in the kernel because Ted Ts'o thinks it's okay to bag on us because R4L uses unstable features.

I am not sure Ted was talking about unstable features used by Rust for Linux.

[traviscross]

Miguel also added that you do not even need to ship it into nightly, you can just give us a modified compiler repository and we can test locally with that.

My understanding from our prior discussions was that RfL was looking for some option you could use to relax coherence for your use case, on nightly, so that you could actually merge this work to break things apart into separate crates, with the idea being that, while we would never stabilize the flag or whatever that would relax the rules in a coarse way, that this nightly ability would allow you to hold onto an older MSRV as, when we do later add something we can stabilize, RfL could use build-time logic to move to that conditionally based on the user's toolchain version.

@ojeda: Let me know about that. If that's no longer the idea, and testing with some local branch is fine for what you need until we later (maybe much later) work out something that could go on a stabilization path, then we can indeed just close this.

[oli-obk]

when we do later add something we can stabilize, RfL could use build-time logic to move to that conditionally based on the user's toolchain version.

I'm pretty confident we'll need years to get even an idea of something stabilizable. This is the kind of feature with too many unknowns to actually be on the horizon. I recommend just waiting until there's an impl and then discussing what to actually do. Especially in the light of linux already able to do a trivial backport of a one line if true {return}

[traviscross]

I'm pretty confident we'll need years to get even an idea of something stabilizable.

Agreed it could. As I put it:

...until we later (maybe much later)...

[joshtriplett]

There have been discussions for many, many years about trying to find ways to relax the orphan rule, and about experimenting with approaches that would allow doing so without introducing soundness issues. This issue was an effort to attempt to turn some of those discussions into low-commitment action and experiment.

I'm not sure why this was framed as being a potential out-of-tree rustc experiment. The discussion in the RfL meeting was about something that could appear in rustc.

In the RfL meeting, I suggested doing two things:

• Running this by the types team first, to figure out if there would be critical issues with adding an unstable, experimental feature to allow opting out of the orphan rule in binary crates. (I realize that the RfL project would eventually want something that works in library crates, but that would need a lot more design, so the proposal here was for a simpler experiment.) This issue is an effort to get that vibe-check, and address any issues that arise.
• Assuming there wasn't a critical issue with trying an experimental flag, we could then try it as a lang experiment, adding it on nightly (behind the extra-experimental flag for incomplete_features) for the purposes of experimentation.

I think it's reasonably safe to say RfL is not going to push upstream any code depending on incomplete_features; I think incomplete_features is a good boundary for "don't use this in production, don't touch this at all unless you're actively working on it". The question is more, how might we start figuring out a path to a feature we could feel confident in and stabilize? If it's going to take a while, taking a first step seems like a good idea.

[oli-obk]

Yea I think bin crates and wasm cdylibs are a safe place for experimentation.

Though I do not see why this should be part of RfL goals or prioritization. It is an issue for everyone, and everyone works around it. So can RfL. There are no blockers or major pain points, just a bit of boilerplate.

Or is the issue that such workarounds create an API that will be expensive to migrate due to the guarantees the kernel has?

[ojeda]

My understanding from our prior discussions was that RfL was looking for some option you could use to relax coherence for your use case, on nightly, so that you could actually merge this work to break things apart into separate crates, with the idea being that, while we would never stabilize the flag or whatever that would relax the rules in a coarse way, that this nightly ability would allow you to hold onto an older MSRV as, when we do later add something we can stabilize, RfL could use build-time logic to move to that conditionally based on the user's toolchain version.

@ojeda: Let me know about that. If that's no longer the idea, and testing with some local branch is fine for what you need until we later (maybe much later) work out something that could go on a stabilization path, then we can indeed just close this.

In the past we discussed whether we could get a flag in the actual compiler that we could use as a last resort (especially nice if it could be in Debian Trixie's rustc). That would be great, of course, and we could discuss the limits on what we are supposed to do with it, e.g. we could consult with you when it gets used and wait for your Ack before committing anything into the kernel that relies on it, so that we don't end up in a situation that the kernel cannot be supported by Rust.

Yesterday, my understanding was that we were discussing other possibilities that are way less adventurous, such as having the flag but not ever use it in Linux. Or, if that is still too risky, having it in a different binary that is not the official rustc so that it was still easier for us to use and experiment with. My understanding is that someone said it would still be easier to just add the flag in nightly. Orthogonally, we also talked about potentially having special diagnostics (e.g. warn by default lint), that would explain where and how the rules are getting broken, but still bypass the orphan rule.

[joshtriplett]

Yea I think bin crates and wasm cdylibs are a safe place for experimentation.

Thank you, that's really helpful confirmation!

I'm assuming this would apply to a C-style staticlib as well? (Noting here the observation people have made that staticlib really should have been called cstaticlib.)

For the sake of clarity: I very much understand that large design issues and potential soundness issues definitely apply to any solution that would allow this in library crates. I'd like to get there eventually, but I would not equate that with the much simpler experiment of trying this in top-level bin/cdylib/staticlib crates.

(I have some ideas for simplifying the problem for library crates as well, but that's separate.)

Though I do not see why this should be part of RfL goals or prioritization. It is an issue for everyone, and everyone works around it. So can RfL.

Many of the items that get noticed in the course of work on RfL apply to many many other projects as well, and work on them (towards eventual stabilization of them) helps many other projects as well. This one seemed worth bringing up on the basis that many many projects have requested this, not just RfL. It's a regular recurring topic on IRLO, URLO, /r/rust, and many other places.

Or is the issue that such workarounds create an API that will be expensive to migrate due to the guarantees the kernel has?

If you mean workarounds like newtypes: there are no API guarantees inside the kernel, so there's no fundamental concern about migration. But it's the kind of thing where it'd probably produce enough of an "ugh" reaction from people using it that I suspect the RfL folks would likely just not split crates if it'd require that workaround, rather than inflict that on people.

[joshtriplett]

@ojeda wrote:

especially nice if it could be in Debian Trixie's rustc

I can safely say this isn't going to happen. The compiler version that's likely to ship in Trixie is well past the point where any experimental flag could be added that RfL could or should be relying on.

My understanding is that someone said it would still be easier to just add the flag in nightly.

✋ Confirming that I said that in the meeting. Adding an experimental flag in nightly is a first step towards something you'll eventually be able to use, and that we'll eventually be able to stabilize.

[ojeda]

there are no API guarantees inside the kernel

Exactly, that is the main motivation for the kernel to relax the rule somehow.

I can safely say this isn't going to happen. The compiler version that's likely to ship in Trixie is well past the point where any experimental flag could be added that RfL could or should be relying on.

Yeah, that was my understanding as well yesterday -- I was trying to describe what we discussed in the past in the first sentence.

That is why, since it is not happening, we were suggesting yesterday other options to start the experiment that may not require the flag in the actual rustc, if that were easier for you.

Of course, it is still better for us to have it in nightly; and if it is also easier for you, that is great too. And in such a case, we would still discuss with you before actually using it in the kernel for real and so on, i.e. the same still applies.

I hope that clarifies.

[oli-obk]

This one seemed worth bringing up on the basis that many many projects have requested this, not just RfL. It's a regular recurring topic on IRLO, URLO, /r/rust, and many other places.

I agree, I just don't like that it's being under a RfL umbrella. It seems like a useless burning of priorization points while actual blockers for running on stable have not finished.

This is not what is going to make RfL any less likely to succeed, so it's burning sync T-lang meeting time and discussion resources. Let's use those resources to instead actually do the experiment as we always do experiments. No pressure, just figuring out MVPs and incremental steps and stuff

[joshtriplett]

I think we're broadly in agreement. It is definitely not a "needed for RfL to be on stable" issue, and as such it also isn't part of that project goal.

It's something I would advocate prioritizing in lang on the basis of "many people want this, and it's a multi-year arc we should embark upon because the sooner we start the sooner we finish".

In any case, 👍 for embarking upon the experiment rather than spending more time evaluating rationale and prioritization. :)

[ojeda]

This is not what is going to make RfL any less likely to succeed

It is true that it is not important because we have kept a lot of the code in a single crate. However, we will really need to split it soon in many crates, and thus this may become more important soon, i.e. it could become a common pain point mentioned by kernel maintainers. We don't know how bad it will be yet, though.

I think we all agree that it is not in the scope of the flagship project goal. Nevertheless, it is something that has been in our radar for a couple years.

[steffahn]

The issue that I am facing currently is not that bad, as I can solve it with an additional trait. But in the long run, it won't be feasible to always create a workaround for orphan rule conflicts.

I would love to see some actual examples of such cases.

---

Note that in the kernel crate, we don't need to be protected by the orphan rule, as all dependents (and dependencies except core) of the kernel crate are under our control directly in-tree.

I’m not sure I follow this argument… well it lacks explicit arguments anyway. I can only assume this argues from a perspective of “orphan rules protect semver-stable interfaces” and “orphan rules protect you from unexpected downstream breakage/overlaps”. But that’s an incomplete picture. I’ve recently written down some of my intuitions of a larger picture here (given this is mostly written from a user’s perspective, I’m not sure every point I’m making is actually correct… but I’m pretty certain with the challenges around vtables). I’m happy to hear any corrections or clarifications if I’m too pessimistic on any aspects.

---

To re-iterate the high-level: The important difficulty with breaking orphan rules is two main aspects:

• without orphan rules, a downstream crate might implement some impl Bar for Foo when Foo and Bar are already available together further upstream: thus there can some compilation (specifically monomorphization) of code involving thee concrete type&trait Foo and Bar where the impl Bar for Foo relation isn’t visible yet.
  • in many places around monomorphization, the compiler makes the assumption that for any known, concrete type Foo and Bar, it is already known whether or not Foo: Bar and this can’t change. Specialization uses this; vtable creation uses this.
  • this limitation is not all that relevant to your use-case as there’s usually some (at least 1) proper choice for the “crate that a trait implementation can be placed into”, anyway. (Sometimes this might mean cross-dependencies across otherwise “leaf” crates; or factoring out a trait-defining crate into its own thing, but if you control the whole code base, it shouldn’t really be an issue.)
• the existence of orphan rules can be depended on by the trait solver itself. Sometimes it’s just really useful to be able to determining “this type can’t implement this trait”, especially for overlap checking, and this negative reasoning logic is defined on the assumption of orphan rules
  • this is an aspect of orphan rules & implementation details I’m less familiar with, so I don’t know how hard it would be to “fix” this, e.g. with some mechanism that turns a “upstream crate saw no possible overlap based on orphan rules, then downstream crate created an overlap anyways because it broke orphan rules” into a guaranteed compilation error downstream. Which turns the soundness issue back into a “semver” issue, i.e. the kind of thing you had in mind to begin with when arguing that “we don't need to be protected by the orphan rule”
  • your use case of Zeroable for Option<Box<T, A>> is interesting and only matches this second case
    • since Box is only defined in kernel (I assume… right?) there is no possibility for this Zeroable for Option<Box<T, A>> impl to be missing in any other crate’s compilation – in fact you could argue that of Option was a #[fundamental] type, then this impl would be legal here
      • I wonder if the right thing to discuss is a “mechanism to mark type constructors as #[fundamental] only for one particular trait” – I’m not sure whether or not the current trait solver needs to make the assumption anywhere that the set of #[fundamental] types is consistent across different traits
    • the workaround (I assume you’re using) of making a helper trait, e.g. ZeroableInOption and a blanket impl Zeroable for Option<T> where T: ZeroableInOption are good in that they also explicitly opt out of the – alternative – ability of local negative reasoning. Without it, you’d be able – inside of the crate defining Zeroable – to negatively reason that no Option<T>: Zeroable bound is ever true; allowing the overlap checker to depend on it, etc…
      • this workaround is essentially simulating the “opt out of #[fundamental]” ability. Perhaps simulating it quite effectively, actually. Of course it might seem more convenient to be able to write the Zeroable for Option<Box<T, A>> directly, but I’d be curious if there really are any actual practical use-cases (of this form where you’d believe “if this type was #[fundamental] I wouldn’t have any problems”) where the workaround doesn’t work.

---

Now… I’ll come back again to the original point: I’m very curious to see more examples. Examples of that “it won't be feasible to always create a workaround for orphan rule conflicts”.

For instance, in my original (linked) internals thread reply I already hadn’t actually thought up the example here at all, with Option covering a type parameter that should be filled with a concrete type downstream. The intuition that disabling orphan rules would always need to work analogously to sending trait implementations [and sometimes corresponding additional dependencies on a crate defining the trait or type in question] to upstream traits apparently was wrong, since the Zeroable for Option<Box<T, A>> wasn’t directly expressible anywhere.

But with this example solved via a ZeroableInOption helper trait, I’m once again at a point where I’m having a hard time imagining what a use-case can look like that couldn’t be addressed by some combination of these mechanisms.

Of course a 3rd possible use-case is when you actually want to somehow be like Foo: Bar can’t be defined here, but I’ll worry about it later, downstream. I can’t imagine that’s what this request to “relax the orphan rules” is about, because it’s clearly not just about orphan rules when you do need to write use-cases for the Foo: Bar upstream already; but still it’s also clear that an upstream API can be annoying to refactor by introducing some generic argument <T: SomeTrait>¹ everywhere when you already know that there’s exactly one downstream implementation that’ll provide it.

This general pattern can come up with orphan-rules considerations though, because I can imagine applying a “moving the otherwise-orphaned impl somewhere upstream” workaround can be hard when the implementation details use a lot of other stuff only available downstream.

Footnotes

1. In relation to Foo: Bar this would be understood that e.g. Foo: Bar is first refactored into some Dummy: Bar<Foo>-style trait, then Dummy is the downstream type that takes the role of T; and SomeTrait is the Bar<Foo>. ↩

[ojeda]

Thanks @steffahn for all the context and explanations. Quick note...

I’m very curious to see more examples. Examples of that “it won't be feasible to always create a workaround for orphan rule conflicts”.

Even if there happen to be always workarounds (which would already be a nice result), part of the motivation here is to avoid those workarounds, i.e. to improve the language (if possible) so that they are not needed to begin with, thus improving ergonomics and making the crate boundary less special (for projects that may want/need that).

[oli-obk]

What steffahn is trying to say is that you're having us poke in the dark. We don't know what you are asking us to experiment with. For that matter, I'm not even sure all the problems being grouped under orphan rules are actually orphan rules.

Please provide examples of the different kinds of workarounds you are considering.

There are proposals I can think of that can be considered if someone writes a thorough enough analysis of the problems with said proposal (what Jack asks for in https://rust-lang.zulipchat.com/#narrow/channel/326866-t-types.2Fnominated/topic/.23136979.3A.20experiment.20with.20relaxing.20the.20orphan.20rule/near/499848638).

And then there are proposals (that have frequently employed workarounds) that to the best of my knowledge have been hard rejected by every lang or compiler dev as long as I've been around rustc.

[ojeda]

What steffahn is trying to say is that you're having us poke in the dark.

I understood -- my reply was just a note on a particular point.

We don't know what you are asking us to experiment with.

We are not asking Rust to experiment with anything in particular. I think @y86-dev's initial message is quite clear on that. @joshtriplett also framed it well: "The question is more, how might we start figuring out a path to a feature we could feel confident in and stabilize? If it's going to take a while, taking a first step seems like a good idea."

We are stating a problem we are facing and we had a suggestion that could perhaps allow us to experiment around how the kernel could potentially look like if some current restrictions (or their workarounds) were not there. The goal of that suggestion is to give you more information about what kind of code we would like to be able to write if possible. The overall goal is to learn more about the problem by using Linux as an example use case where we already collaborate.

For that matter, I'm not even sure all the problems being grouped under orphan rules are actually orKhan rules.

Definitely, that is a possibility. What we care about is the problem and whether there is anything that could potentially be done about it to improve how kernel code is written.

There are proposals (...)

That is good to know, thank you. However, to be clear, we are not trying to propose any particular solution.

[oli-obk]

how might we start figuring out a path to a feature we could feel confident in and stabilize?

By splitting your crates the with the "workarounds" (I disagree they are really workarounds. They make reasoning about what happens where very simple) and reporting actual end user pain points.

[oli-obk]

I chatted with @compiler-errors about this a bit. As we talked about during the RfL meeting, what you actually need for this specific issue is the ability to define fundamental types. Now, this is not something we can expose on stable for the foreseeable future because it's a semver hazard, but

• it's completely sound
• will never be removed
• unlikely to change any time soon and when it will the cost of keeping it around for years while you migrate to a stable version seems low

So, my recommendation is that you try out this feature in your experiment. No new flags needed. If you decide it would be useful and solve most or all of your problems with crate splitting, let's discuss how to get it to you on stable. Old compilers can then just use the current overly permissive attribute

[ojeda]

We can definitely give that a try, thanks a lot!