rfcs/text/1643-memory-model-strike-team.md

• Feature Name: N/A
• Start Date: 2016-06-07
• RFC PR: rust-lang/rfcs#1643
• Rust Issue: N/A

Summary

Incorporate a strike team dedicated to preparing rules and guidelines for writing unsafe code in Rust (commonly referred to as Rust's "memory model"), in cooperation with the lang team. The discussion will generally proceed in phases, starting with establishing high-level principles and gradually getting down to the nitty gritty details (though some back and forth is expected). The strike team will produce various intermediate documents that will be submitted as normal RFCs.

Motivation

Rust's safe type system offers very strong aliasing information that promises to be a rich source of compiler optimization. For example, in safe code, the compiler can infer that if a function takes two &mut T parameters, those two parameters must reference disjoint areas of memory (this allows optimizations similar to C99's restrict keyword, except that it is both automatic and fully enforced). The compiler also knows that given a shared reference type &T, the referent is immutable, except for data contained in an UnsafeCell.

Unfortunately, there is a fly in the ointment. Unsafe code can easily be made to violate these sorts of rules. For example, using unsafe code, it is trivial to create two &mut references that both refer to the same memory (and which are simultaneously usable). In that case, if the unsafe code were to (say) return those two points to safe code, that would undermine Rust's safety guarantees -- hence it's clear that this code would be "incorrect".

But things become more subtle when we just consider what happens within the abstraction. For example, is unsafe code allowed to use two overlapping &mut references internally, without returning it to the wild? Is it all right to overlap with *mut? And so forth.

It is the contention of this RFC that a complete guidelines for unsafe code are far too big a topic to be fruitfully addressed in a single RFC. Therefore, this RFC proposes the formation of a dedicated strike team (that is, a temporary, single-purpose team) that will work on hammering out the details over time. Precise membership of this team is not part of this RFC, but will be determined by the lang team as well as the strike team itself.

The unsafe guidelines work will proceed in rough stages, described below. An initial goal is to produce a high-level summary detailing the general approach of the guidelines. Ideally, this summary should be sufficient to help guide unsafe authors in best practices that are most likely to be forwards compatible. Further work will then expand on the model to produce a more detailed set of rules, which may in turn require revisiting the high-level summary if contradictions are uncovered.

This new "unsafe code" strike team is intended to work in collaboration with the existing lang team. Ultimately, whatever rules are crafted must be adopted with the general consensus of both the strike team and the lang team. It is expected that lang team members will be more involved in the early discussions that govern the overall direction and less involved in the fine details.

History and recent discussions

The history of optimizing C can be instructive. All code in C is effectively unsafe, and so in order to perform optimizations, compilers have come to lean heavily on the notion of "undefined behavior" as well as various ad-hoc rules about what programs ought not to do (see e.g. these three posts entitled "What Every C Programmer Should Know About Undefined Behavior", by Chris Lattner). This can cause some very surprising behavior (see e.g. "What Every Compiler Author Should Know About Programmers" or this blog post by John Regehr, which is quite humorous). Note that Rust has a big advantage over C here, in that only the authors of unsafe code should need to worry about these rules.

In terms of Rust itself, there has been a large amount of discussion over the years. Here is a (non-comprehensive) set of relevant links, with a strong bias towards recent discussion:

• RFC Issue #1447 provides a general set of links as well as some discussion.
• RFC #1578 is an initial proposal for a Rust memory model by ubsan.
• The Tootsie Pop blog post by nmatsakis proposed an alternative approach, building on background about unsafe abstractions described in an earlir post. There is also a lot of valuable discussion in the corresponding internals thread.

Other factors

Another factor that must be considered is the interaction with weak memory models. Most of the links above focus purely on sequential code: Rust has more-or-less adopted the C++ memory model for governing interactions across threads. But there may well be subtle cases that arise we delve deeper. For more on the C++ memory model, see Hans Boehm's excellent webpage.

Detailed design

Scope

Here are some of the issues that should be resolved as part of these unsafe code guidelines. The following list is not intended as comprehensive (suggestions for additions welcome):

• Legal aliasing rules and patterns of memory accesses
  • e.g., which of the patterns listed in rust-lang/rust#19733 are legal?
  • can unsafe code create (but not use) overlapping &mut?
  • under what conditions is it legal to dereference a *mut T?
  • when can an &mut T legally alias an *mut T?
• Struct layout guarantees
• Interactions around zero-sized types
  • e.g., what pointer values can legally be considered a Box<ZST>?
• Allocator dependencies

One specific area that we can hopefully "outsource" is detailed rules regarding the interaction of different threads. Rust exposes atomics that roughly correspond to C++11 atomics, and the intention is that we can layer our rules for sequential execution atop those rules for parallel execution.

Termination conditions

The unsafe code guidelines team is intended as a temporary strike team with the goal of producing the documents described below. Once the RFC for those documents have been approved, responsibility for maintaining the documents falls to the lang team.

Time frame

Working out a a set of rules for unsafe code is a detailed process and is expected to take months (or longer, depending on the level of detail we ultimately aim for). However, the intention is to publish preliminary documents as RFCs as we go, so hopefully we can be providing ever more specific guidance for unsafe code authors.

Note that even once an initial set of guidelines is adopted, problems or inconsistencies may be found. If that happens, the guidelines will be adjusted as needed to correct the problem, naturally with an eye towards backwards compatibility. In other words, the unsafe guidelines, like the rules for Rust language itself, should be considered a "living document".

As a note of caution, experience from other languages such as Java or C++ suggests that the work on memory models can take years. Moreover, even once a memory model is adopted, it can be unclear whether common compiler optimizations are actually permitted under the model. The hope is that by focusing on sequential and Rust-specific issues we can sidestep some of these quandries.

Intermediate documents

Because hammering out the finer points of the memory model is expected to possibly take some time, it is important to produce intermediate agreements. This section describes some of the documents that may be useful. These also serve as a rough guideline to the overall "phases" of discussion that are expected, though in practice discussion will likely go back and forth:

• Key examples and optimizations: highlighting code examples that ought to work, or optimizations we should be able to do, as well as some that will not work, or those whose outcome is in doubt.
• High-level design: describe the rules at a high-level. This would likely be the document that unsafe code authors would read to know if their code is correct in the majority of scenarios. Think of this as the "user's guide".
• Detailed rules: More comprehensive rules. Think of this as the "reference manual".

Note that both the "high-level design" and "detailed rules", once considered complete, will be submitted as RFCs and undergo the usual final comment period.

Key examples and optimizations

Probably a good first step is to agree on some key examples and overall principles. Examples would fall into several categories:

• Unsafe code that we feel must be considered legal by any model
• Unsafe code that we feel must be considered illegal by any model
• Unsafe code that we feel may or may not be considered legal
• Optimizations that we must be able to perform
• Optimizations that we should not expect to be able to perform
• Optimizations that it would be nice to have, but which may be sacrificed if needed

Having such guiding examples naturally helps to steer the effort, but it also helps to provide guidance for unsafe code authors in the meantime. These examples illustrate patterns that one can adopt with reasonable confidence.

Deciding about these examples should also help in enumerating the guiding principles we would like to adhere to. The design of a memory model ultimately requires balancing several competing factors and it may be useful to state our expectations up front on how these will be weighed:

• Optimization. The stricter the rules, the more we can optimize.
  • on the other hand, rules that are overly strict may prevent people from writing unsafe code that they would like to write, ultimately leading to slower execution.
• Comprehensibility. It is important to strive for rules that end users can readily understand. If learning the rules requires diving into academic papers or using Coq, it's a non-starter.
• Effect on existing code. No matter what model we adopt, existing unsafe code may or may not comply. If we then proceed to optimize, this could cause running code to stop working. While RFC 1122 explicitly specified that the rules for unsafe code may change, we will have to decide where to draw the line in terms of how much to weight backwards compatibility.

It is expected that the lang team will be highly involved in this discussion.

It is also expected that we will gather examples in the following ways:

• survey existing unsafe code;
• solicit suggestions of patterns from the Rust-using public:
  • scenarios where they would like an official judgement;
  • interesting questions involving the standard library.

High-level design

The next document to produce is to settle on a high-level design. There have already been several approaches floated. This phase should build on the examples from before, in that proposals can be weighed against their effect on the examples and optimizations.

There will likely also be some feedback between this phase and the previous: as new proposals are considered, that may generate new examples that were not relevant previously.

Note that even once a high-level design is adopted, it will be considered "tentative" and "unstable" until the detailed rules have been worked out to a reasonable level of confidence.

Once a high-level design is adopted, it may also be used by the compiler team to inform which optimizations are legal or illegal. However, if changes are later made, the compiler will naturally have to be adjusted to match.

It is expected that the lang team will be highly involved in this discussion.

Detailed rules

Once we've settled on a high-level path -- and, no doubt, while in the process of doing so as well -- we can begin to enumerate more detailed rules. It is also expected that working out the rules may uncover contradictions or other problems that require revisiting the high-level design.

Lints and other checkers

Ideally, the team will also consider whether automated checking for conformance is possible. It is not a responsibility of this strike team to produce such automated checking, but automated checking is naturally a big plus!

Repository

In general, the memory model discussion will be centered on a specific repository (perhaps https://github.com/nikomatsakis/rust-memory-model, but perhaps moved to the rust-lang organization). This allows for multi-faced discussion: for example, we can open issues on particular questions, as well as storing the various proposals and litmus tests in their own directories. We'll work out and document the procedures and conventions here as we go.

Drawbacks

The main drawback is that this discussion will require time and energy which could be spent elsewhere. The justification for spending time on developing the memory model instead is that it is crucial to enable the compiler to perform aggressive optimizations. Until now, we've limited ourselves by and large to conservative optimizations (though we do supply some LLVM aliasing hints that can be affected by unsafe code). As the transition to MIR comes to fruition, it is clear that we will be in a place to perform more aggressive optimization, and hence the need for rules and guidelines is becoming more acute. We can continue to adopt a conservative course, but this risks growing an ever larger body of code dependent on the compiler not performing aggressive optimization, which may close those doors forever.

Alternatives

• Adopt a memory model in one fell swoop:
  • considered too complicated
• Defer adopting a memory model for longer:
  • considered too risky

Unresolved questions

None.