Rust memory management: Reasoning from local scope - part 1

Thu, Mar 11, 2021 ❝A from-local-scope way to think about memory management in Rust that allows understanding and working with the borrow-checker instead of against it.❞

Contents

Disclaimer This article is written with the experience level of someone who is learning about memory management, the borrow-checker, and Rust in general. Given that I have experience with other languages, I will allow myself to reason about the mechanisms in rust and its differences, as a way to thoroughly comprehend. Invariably there will be subtleties that are incorrect and/or details in the actual mechanisms that I missed. This article is not a complete picture. Nevertheless, this way of reasoning should hold in general and may help you get into the right mindset to work with the language, its borrow-checker and other analysis tools, instead of against them.

The notion of borrowing in a programming language is not a complicated concept. It is straight-forward, really. Rust implemented the borrow-checker: a compile-time analysis that evaluates use of data (memory) and enforces strict data-safety rules. The borrow-checker is notorious for being the single most prevalent analyzer that you are in conflict with while learning the language, that is, writing your lines of code. However, the borrow-checker is not the issue. It is the requirement to think local-first.

Local scope

Borrowing isn’t a complicated concept. Instead, it’s the fact that you are expected to reason locally, which is not even very clear at first. And to add to the problem, the programmer - especially those with experience in other languages - will have a clear high-level picture of what they want to accomplish. However, they struggle to express this in the necessary detail in the programming language:

1. Use memory for data processing.
2. … some/many high-level processing steps …
3. Profit!

The issue is in step 2: many of the existing programming languages allow taking shortcuts. Either, because the type systems is flexible enough to allow this - the language provides high-level abstractions who fill in these gaps. Or, memory management is advanced enough to automatically account for implicit steps through use of analysis, such as liveness checks in garbage collection runs, the use of aliases for the breadth to which data is accessible, and escape analysis during compilation to choose a suitable destination for memory: stack and heap.

Rust, however, is designed to give full control to the programmer. It does not do this in the background, as an abstraction. Rust expects you to make “every” step explicit, hence forces you to reason about everything from the local scope (only). The root is the stack, i.e. the logic in the current function.

Heap memory, shared references, anything more complicated than a single, unique piece of memory is provided through a local object of a type whose purpose is to provide such capability. Understanding how to satisfy the borrow-checker means understanding from what vantage point to start reasoning and to pick the right type - or composition of types - to satisfy all your memory requirements. Furthermore, keeping things simple means you get really trivial, easy-to-read code. The more complicated the expectations and interactions with memory, the more complicated and/or elaborate your type.

Memory management: the stack

Rust does not hide the fact that it operates on regions of memory. An elaborate struct-type will either be fully mutable or fully immutable. The struct’s memory region is treated the same as the single-byte memory region of a type u8 variable. Uses that demand more subtle management are constructed through the use of dedicated single-purpose types.

Programs work with the concept of a stack and a heap. The stack is the predefined memory, e.g. local variables, that are present in the currently executing function. Stack-memory is allocated when the function is entered, and the memory is cleaned up (destroyed) when the function ends. There is no explicit “memory management” necessary, as the memory lives exactly as long as the function takes to execute. This is very strict, very predictable, very controllable, and limiting.

Limitations are not always bad. There are restricted programming practices that eliminate classes of bugs by programming with a stack-only model. These practices are used for very high-risk applications.

On the stack, you cannot allocate unknown-sized amounts of memory, or very large amounts of memory, or let memory live for longer than the function execution, or arbitrarily share the memory. These limitations come with the model.

For large amounts of memory or memory that should survive for arbitrary amounts of time, memory that should be shared among threads, or any other elaborate use case, the heap is required.

The heap is “the rest of the memory”, which can be more-or-less arbitrarily used. However, given that its allocation, deallocation, use, access-level/protection, is arbitrary. It requires some form of (manual) management. This management comes in different flavors, from manually managed to fully automated using hints, compile-time analysis and/or run-time prediction.

Rust uses the borrow-checker to extend its control over memory and analysis to comprehend at compile-time how memory is used and whether it is used appropriately. Effectively, it extends the reach of - in the basis - a restrictive model. Note that, although many languages work with the stack first, rust relies on it strictly due to extensive analysis.

Memory management: types

There are types for various purposes. We will look at the most important types. These types are what enables the use of certain constructions and/or behaviors regarding the control of memory. Each of these types controls its memory region in a specific way.

Fundamental analysis markers:

These traits “mark” a type such that the type is recognized to possess certain qualities (or lack thereof) and can/should be used in a certain way.

• std::marker::Sized/?Sized markers.
  • implicit, by default, on everything except Self, due to nature of traits.
  • fundamental indicator used for memory allocation, i.e. indicates size known at compile-time, which is a requirement for (default) allocations.
• std::marker::Copy: enable copying of memory - simply copying the bits. (implicit)
• std::marker::Send: enabling transfer between threads.
• std::marker::Sync: safe for referencing from multiple threads.
• std::marker::Unpin: exists to relieve the pinning-restriction for a specific type. (see std::pin - pinning)

Memory control:

These traits indicate certain expectations w.r.t. to the use of memory of this type.

• std::clone::Clone: alternative to Copy that allows cloning of complicated structures of memory.
• std::ops::Drop: destructor (req.!Copy)
• std::pin::Pin: an indicator to prevent moving memory referenced by a (raw) pointer, e.g. a self-referential structure which contains a pointer to itself. (std::pin - pinning)

Moving memory (by definition) implies that memory does not need to be cleaned up yet. Drop::drop(&mut self) is therefore not called yet. The scope for this memory gets extended because it is moved into the next local scope.

Allocation management:

These types provide certain mechanisms for managing regions of memory in the non-trivial way. They allow wrapping the intended type to provide the original type with more liberties.

• use heap memory: std::boxed::Box
• single-field (inner) mutability for immutable struct:
  (internal primitive used for mutability: std::cell::UnsafeCell)
  • std::cell::Cell for owned memory
  • std::cell::RefCell for references (borrowed memory)
• multiple references (reference counting):
  • std::rc::Rc (vanilla reference)
  • std::sync::Arc (thread-safe)
  • std::rc::Weak (non-owning reference)

The list of types (and type-classes) mentioned above is not exhaustive. It does, however, contain the most elementary concepts and types that enable complicated composites in terms of memory locations, memory allocation mechanisms and memory management hooks.

Construction/structure

Managing “memory space” for use in a program is one aspect. Another aspect is the structure of the memory that is used. This can be a particular layout, or a common subset of features/fields, or the alignment of fields. Memory can be used in a sufficiently flexible and interchangable way without violating any rules that would compromise its content.

Structs

A struct represents - to the extent relevant in this topic - a composite memory region consisting of one or more fields, each with its own type. A structure is allocated as a contiguous memory region and are used to group and manage related content as a whole.

Rust manages memory regions as a whole, including that of a struct. A struct’s memory is therefore marked either fully mutable or fully immutable. The memory management types that are available, can subsequently be used to add fine-grained control over individual struct fields.

Rust allows defining methods on a struct type. This acts as a natural mechanism for encapsulation: methods for controlled access, where these dedicated methods are aware of the rules regarding field mutation, i.e. the state invariants.

Generics: Traits

There are two keywords to distinguish between two ways of using generic types:

• impl indicates the code should be specialized at compile-time, for the type that is used. The usage pattern must solidly use a single type for each instance. Multiple occurrences, each with a different type, implies multiple implementations are generated during compilation.
• dyn indicates code that should expect any of the trait-satisfying types to be provided. Multiple types can be mixed up as long as the satisfying trait gets implemented. The mechanism called dynamic dispatch is used to at-runtime determine to address each instance by its common operations, i.e. implemented trait.

unsafe

Due to the reliance on locally-scoped analysis of the borrow-checker, it is impossible to prove some constructions sound. unsafe allows for special exception such that logic that cannot be proved sound in the local scope, can still be implemented.

The unsafe semantics require the developer to ensure correct memory management according to the same standards as safe rust. This is, however, assumed correct instead of being fully verified. Unpredictability and undefined behavior should not happen in safe rust, but may happen in unsafe blocks due to the responsibility for soundness being deferred to the developer.

Code containing unsafe should be most prevalent inside the standard library to provide the most elementary types. However, if necessary, the mechanism is available to all developers. It is recommended, however, to use unsafe as sparingly as possible.

Conclusion

We have mostly looked at some individual features used by compiler and static analysis, such as the borrow-checker, for verifying program code. We will go into more reasoning in a follow-up.