about

09/17/2022

RustBites - Safety

Rust Bite - Safety

Rust is safe by construction via compiler enforcements

1.0 Why Rust?

Rust is an interesting language, combining memory safety of C# and Java with performance of C++. Unlike these languages, Rust also provides data race safety by construction.

Using modern idioms, one can build, with C++, memory safe programs without data races. But when building large systems, with many thousands of lines of code, it is easy to forget, in a few of those lines, to use an idiom or unintentionally share data between threads without proper locking. C++ is memory and data race safe by convention.

Rust, however, ensures memory and data safety by construction. Code with unsafe memory access and data races will fail to compile. It accomplishes that with an intersting ownership model. We go over the details below, and explore code in several other Bites, e.g., Undefined Behavior and Ownership.

2.0 Memory Safety

Memory Safety means that a program cannot read or write to memory it does not own, so memory safe code:

Can not construct uninitialized references.
Can not allow references to become invalid due to a reallocation of memory by the referend.
This could be caused by a vector, with a reference to its interior, reallocating to make room for additional data.
References can not outlive instances they reference.
Can not read from, or write to, memory accessed by indexing beyond the size of any indexable collection.

To see what could happen without these constraints, look at Undefined Behavior with C++. Modern C++ has facilities and idioms that prevent undefined behavior by convention. We will see that Rust does so by construction.

The purpose of Rust's safety mechanisms is to prevent unsound code by refusing to build it. Rust chooses to to reject some safe programs in order to reject all unsafe programs, e.g., its hueristics result in occasional false positives - claiming a sound program is unsound, but no false negatives. We will have more to say about this in Section 7.

This is a "Rust Short" - a brief video presenting a Rust Safety "thought experiment".

You will probably want to view "picture-in-picture" or "full-screen" so details are large enough to be seen easily.

Running as "picture in picture" allows you to move to other web pages while still watching and listening to the video.

3.0 Rust Safety Invariants

Rust ensures memory safety, for all code outside unsafe blocks, by enforcing two invariants:

Safe referencing - No shared mutabilty through references.
Safe indexing - All collections, including native arrays, are sized, and any attempt to index outside that sized area results in a panic, e.g., an orderly shutdown of the current thread before any reads or writes can complete.

Using these two simple invariants as programming guides will make working with Rust easier. The first invariant often causes problems for developers new to Rust when working with linked data structures.

Fig 1. Directed Graph using references

Fig 2. Directed Graph using vector indexes

Note that the first invariant is a very strong condition. There are useful program constructs, like directed graphs, that depend on shared mutability to function as expected. A child graph node, like node 0 in Fig 1., may be shared between several parents and without mutation of the node's value we could only build constant graphs.

We can build non-constant directed graphs using Rust. We cannot easily construct graph edges using references. If we move all graph nodes into a vector, then each parent can refer to its children using vector indices. We will need to handle node deletions and reuse slots, but that is straight forward.

A program can safely share mutability through vector indices because indexes remain valid over vector buffer reallocation when adding new nodes. The first safety invariant applies to references, but not to indexes.

Several years ago, before learning Rust, I built a C++ Directed Graph class using the strategy suggested above. I found that was the easiest way to build a memory safe structure, even though, unlike Rust, C++ would allow me to use pointers to establish parent-child relationships.

The message is that the safety mechanisms used by Rust may lead us to write some small part of our code using different strategies than we would with C++ or other modern languages. And that is eventually a good thing.

4.0 Ownership - static analysis

Rust rejects unsafe programs at compile time with ownership rules derived from the "no shared mutability through references" invariant.

Ownership Rules:

There is only one owner for every data item. That owner is responsible for deallocating the data when it goes out of scope. It does that with a drop operation, very like a C++ destructor invocation.
Ownership can be transferred with move operations.
Ownership can be borrowed by creating references.
Any number of readers (immutable references) may have access to a data value simultaneously.
Writers (mutable owner or mutable reference) get exclusive access to a value - no other readers or writers.

Borrowing from an owner inhibits owner from mutating its data. Mutably borrowing inhibits all other borrows.

It can be a bit complicated to evaluate these rules when you first start creating Rust code. But you don't have to. The Rust compiler does a great job of reporting errors with just the right amount of detail, and often provides a suggested solution.

Rust checks these rules with static analysis by a "borrow-checker". The checker is attempting to determine if you violated the "no shared mutability with references" invariant.

5.0 Non-lexical Filters - refining static analysis

No build environment can accept and build every safe program and reject every unsafe program. As a consequence, Rust is conservative. It chooses to reject some safe programs to insure that it rejects all unsafe programs.

Rust reduces the number of false alarms generated by the Ownership Rules with a couple of additional filters.

Calling a function with one or more immutable references following a mutable borrow will build successfully, since no data in the function can be mutated while the function is being invoked. The same is true of other types of expressions that take immutable references.
Creating and using an immutable reference in the scope of a mutable reference will build if, and only if, the mutable reference is not used after declaration of the immutable reference.

The Rust community calls these non-lexical scope rules.

6.0 Interior Mutability - invariant analysis at run-time

There are blocks of code that do not violate the "no shared mutability of references" invariant but fail static analysis, because they violate the Ownership rules, stated above, but never share mutability because of the way they operate in time. For example, you might wish to create a constant collection, but can't initialize it until runtime, e.g., some values are not known at compile time. So you want to mutate it once, then provide immutable shared access.

Rust provides a construct called RefCell<T> that appears to the compiler to be immutable, but from which code can extract both mutable and immutable references. That doesn't allow you to violate the invariant, because it checks at run-time each borrow, looking for shared mutability. If your program does have concurrent mutable and immutable borrows, using RefCell<T>, it will panic, terminating the thread on which it runs.

In the initialization example, above, we can build the collection values with a single mutable reference obtained from RefCell<the_collection>, but never use it again. Your code can then take mulitple immutable references, as needed, to view the collection. This won't fail to build due to the non-lexical scope filter, and will not fail at run-time since there is no concurrent mutation and aliasing.

Note that, for single threaded programs, we would only resort to run-time checking with RefCell<T> when static analysis results in a false alarm, due to the (small additional) expense of run-time checking.

Rust uses this same run-time checking process for threads that need to share and mutate data by using a Mutex<T> which is similar to a thread safe version of RefCell<T>. It holds both the protected data and a lock. A great benefit of Rust's design is that Mutexes protect specific data, not critical sections of code, so there is no chance of accidentally allowing two threads to use different locks to access the "protected" data, e.g., they share the Mutex which wraps the data. They don't share the data inside a protected area.

7.0 Evaluating Safety

In this final section we circle back to the question: in the presence of safety checking, "is it possible that Rust prevents us from building some safe program." We look at that with a thought experiment.

Figure 1. Soundness Metaphor

Suppose that we could map program activities into the x-y plane, as shown in Figure 1. - don't quibble, this is a metaphor. Further, suppose that we can measure the effort required to separate sound code from unsound code exactly, as shown by the soundness boundary. As we approach the boundary we have to spend more evaluation time, and be very clever, to determine if a program is sound.

Clearly, that is not feasible for a practical compiler, so instead, Rust chooses a simpler evaluation strategy, as outlined in sections 2. and 3. That simplified strategy creates a second boundary inside the soundness region which is relatively easy to evaluate, but will reject some sound programs. Rust chooses to reject some safe programs to insure that it rejects all unsafe programs.

So every program activity in area (1) is proveably sound and compiles; every activity in area (2) is sound, but cannot be easily proven to be so, and does not compile. This may worry you. Suppose a program you are developing requires some program activities between the two boundaries, e.g., sound, but not easily evaluated as sound. Compilation will fail and the compiler's error messages will tell you why it failed.

There are three things that you can do to resolve this issue:

Much of the territory between the boundaries, i.e., region #2, is covered by Rust standard types, which use unsafe blocks that are very carefully vetted by the development team to be sound. So your program simply uses one or more of those types without directly using unsafe blocks.
Consider the standard library's vector. Some of its operations clearly violate the scope-based rule about no shared mutability. It holds a reference to its internal memory, but will hand out a mutable reference to your program. That is safe because the vector (and compiler) conspire to manage change on your behalf by refusing to mutate when there are outstanding references. If you are curious you can look at unsafe blocks in vector from its source documentation.
We use the vector, the compiler doesn't complain because of vector's few small well crafted unsafe blocks, and we benefit from the library developer's expertise.
Seldom do you know your program is walking in the valley of "hard to evaluate region #2" You just use the standard library types and all is well.
In some of that territory, program operations don't violate the invariants, but that can't be determined via static analysis, e.g., there is no simultaneous shared mutation using references because of the way the program operates in time. But that cannot be evaluated statically. For this case one may use "interior mutability", discussed in section 6.
The design may be changed to avoid violating invariants, often by using indexing instead of references, like the directed graph class we mentioned above.

You don't need to think about all this when developing code. The compiler will do the low-level thinking for you. It does help to understand why the language works the way it does and understand why it works so well.

Productivity Tips

Here are some tips that may make you more productive:

Use the Rust library linked types (HashMap, linked_list, ...) instead of trying to craft your own.
Find alternatives to custom linked data structures, as we did for the graph type discussed above. That will usually involve use of vectors.
Pass arguments to functions by reference. If you pass by value the caller's argument will be moved into the function and become permanently invalid in the caller's scope.
In methods of a type you've developed return a member value by reference. Otherwise it would be moved to the caller and the member becomes invalid. If returning by value is important for ergonomic reasons you can return a clone by value, incurring the performance penalty of making a clone.
For all other functions, return a locally created object by value so the data is moved to the caller. That's fast and the returned data continues to be valid. In this case, Rust won't let you return by reference, citing lifetime issues.

You may encounter coding contexts where you would elect not to use one of these tips, but that will happen infrequently.

After writing a lot of Rust code - more than 20 repositories - I never had to use unsafe blocks or write contorted code to build projects. And it was't that hard. The compiler's error messages are so good that it guides you to a sound implementation.

7.0 References:

Reference	Description
Jon Gjengset	Considering Rust - why should you explore Rust?
intorust.com	Excellent discussion of ownership and safety by an expert in five short videos.
Temporarily opt-in to shared mutation	Blog by Alice Ryhl, a primary maintainer of the Tokio crate.
Rust: Unsafe in Rust: Syntactic Patterns	Interesting analysis of unsafe in crates reported by Alex Ozdemir
Rust: A unique perspective	Best description of Rust ownership and sharing that I've found. Check it out!
RustTour.pdf	Quick tour of the Rust programming language emphasizing its unique attributes.
Why Rust for safe systems programming - Microsoft	Microsoft is exploring Rust for system programming.
The Rust Book - Ownership	Ownership rules with examples and discussion
Rust edition-guide	Non-lexical lifetimes
Rust Book	RefCell<T> and the Interior Mutability Pattern