Rust's Many Pointers

Prerequisites

• All of the previous chapter
• Lifetime syntax
• Arrays
• Clone vs Copy vs Move semantics

Rust is a strange hybrid among programming languages in that it combines low-level features allowing a great degree of control over the memory layout of your program with functional features find in more high-level programming languages that generally don't worry themselves with the memory at all or other implementation details at cost of performance without becoming a behemoth like C++ has become in recent years.

A hallmark of lower level control in a programming language is that pointers are not abstracted away. If you are coming from C, you are likely familiar with plain pointers, if you used C++ in the past, you will know that there are many kinds of pointers.

Rust features both plain and smart pointers. Smart pointers either have extended functionality over plain pointers or carry semantics.

The Rust standard library and more broadly speaking, Rust ecosystem features a number of pointers. In this part, we will examine the common use cases of the built-in pointer types and smart pointers from the standard library.

If you happen to be unfamiliar with the concept of pointers, you can check out the Wikipedia or a relevant C tutorial section, these tend to explain the concept of pointers quite well.

Raw Pointers (*const T and *mut T)

The simplest pointers in Rust are the raw pointers. They are roughly equivalent to C's pointers. In Rust, usage of these pointers teeters on the edge of unsafe.

As a rule of thumb, you don't need to use the unsafe {} block to create them, but you need it to be able to de-reference them.

This is because raw pointers are, as the name suggests, raw and simple, and are not subject to Rust's safety nets. A raw pointer does not have a lifetime, is not subject to the the borrow checker and thus can be a pathway to serious memory safety errors commonly found in C code.

#![allow(unused)]
fn main() {
let number: usize = 14;

// it is safe to create a raw pointer
// you generally do this by casting an appropriate borrow with the `as` keyword
let ptr: *const usize = &number as *const usize;

// however, dereferencing a raw pointer requires an unsafe block
unsafe {
    let number_from_ptr: usize = *ptr;
    println!("{}", number_from_ptr);
}
}

One should be wary when using raw pointers, as Rust does not prevent you from doing something like this:

#![allow(unused)]
fn main() {
let string: String = String::from("Morituri te salutant");
let ptr: *const String = &string as *const String;


drop(string); // string dropped and de-allocated here

// ptr is now a dangling pointer
// dereferencing it is UB and in the better case,
// will cause your program to crash
//
// also note that we have to cast to &String,
// unlike the previous example, where `usize: Copy + Clone`,
// we can't move out of a string pointer, as it is only Clone
unsafe {
    let string_from_ptr: &String = &*ptr;
    println!("{}", string_from_ptr);
}
}

Raw pointer usage

Usage of raw pointers in Rust is rather limited and they should be used as infrequently as possible. They do not provide safety guarantees and it is easy to make a mistake in their usage when meshed together with Rust's ownership system.

If it is necessary to use raw pointers, they should only be kept within structures, used as scarcely as possible and great care should be taken they do not cause undefined behavior or memory corruption.

Safe API should never expose raw pointers to the end-users of your code.

FFI

The primary domain of raw pointers is FFI (Foreign Function Interface), or in other words, Rust's interop story. Other languages don't have the notion of Rust's pointers and, thus, plain pointers remain the common denominator when talking to foreign code.

Several precautions need to be taken:

1. You should be wary how you handle owned values you pass raw pointers to around. Make sure no pointers exist when the owned pointee is dropped.
2. Rust's standard types likely make little sense to foreign code. One must generally use C-specific types for which the standard library contains bindings and/or zero-cost wrappers, namely for example CString and CStr (as mentioned in the chapter on ownership). There is also a maintained and blessed binding library for libc, which provides type and other items' definitions from the C standard library. It is considered a poor practice to use even Rust's native primitive types instead of libc ones, as the Rust ones' memory representation may change on different platforms, rendering your code incompatible or prone to undefined behavior
3. Unsafe code should be properly wrapped, encapsulated and hopefully isolated from other parts of your project. Conventionally, bindings to C/C++ libraries are split into two or more crates with one of them actually binding to the library and produces raw unsafe bindings, whereas another provides a safe Rustic API on top of it.

Black magic

Raw pointers are also used for some advanced Rust tricks, such as exploiting implementation details or implementing code that circumvents Rust's ownership model in one way or another.

In Rust, you will find Raw pointers for instance in the implementations of Iterators or containers providing interior mutability. As interior mutability allows you to mutate data inside a container that you only have access through &Container<T>, it is necessary to bypass the fact that you can't mutate safe Rust data through an immutable borrow.

Several other techniques are used, but they are beyond the scope of this chapter. A particular case we encountered in the past is how to properly compare pointers to trait objects.

As shown in the object safety chapter of Advanced Rust Traits, the correct solution ended up being this:

#![allow(unused)]
fn main() {
&*trait_obj as *const _ as *const () == &*trait_obj2 as *const _ as *const ()
}

Borrows (&'a T and &'a mut T)

Borrow pointers are the most commonly encountered type of pointers in Rust. They are one of the cornerstones of Rust's ownership model, as explained in Ownership and string slices.

Each borrow has an explicit lifetime which is in safe Rust dictated by the value it points to. This is an upper limit however, as Rust allows (and often does) shortening of lifetimes.

#![allow(unused)]
fn main() {
fn foobar<'a, 'b>(x: &'a i32, _y: &'b i32) -> &'b i32
where
    'a: 'b
{
    x
}
}

This code example illustrates the shortening of lifetimes and roughly reads as

For a pair of lifetimes 'a and 'b, such that 'a is a lifetime at least as long as 'b, take two parameters of types &'a i32 and &'b i32 and return the first the 'a reference shortened to lifetime &'b Notice that if you swap the lifetimes in the where clause, Rust will complain as lengthening a lifetime is not a safe operation.

Also keep in mind that lifetime on a reference only dictates the certain validity of said reference, not when the pointee will be freed or moved. An owned value may well end up being thrown into mem::forget() (which is a safe operation as memory leaks do not cause undefined behavior or memory corruption), never being freed at all.

Borrow usage

Borrows are used all over Rust code practically everywhere. As they are faster and less resource intensive (it costs to move a value and it may end up copying anyway), they should be preferred unless semantics of your program require something else.

It is also important to note that not all borrows are made equal. &T might, under the hood, either be a raw pointer or a fat pointer. A fat pointer contains the size of the pointee and in Rust, pointers to slices and trait objects are fat pointers.

In general, all dynamically-sized types (with the exception of interop extern types), such as Path, are used behind fat pointers.

// sizes in bytes on my 64-bit system
fn main() {
    /*  8 */ println!("{}", std::mem::size_of::<&usize>());
    /*  8 */ println!("{}", std::mem::size_of::<&mut usize>());
    /* 16 */ println!("{}", std::mem::size_of::<&[usize]>());
    /* 16 */ println!("{}", std::mem::size_of::<&dyn std::fmt::Display>());
    /* 16 */ println!("{}", std::mem::size_of::<&std::path::Path>());
}

Boxes (Box<T>)

Boxes are the first actual smart pointer type encountered in Rust. A box is a pointer type for heap allocation. Whereas &T can point anywhere, and more often than not points to stack, as that is the default for Rust allocations, a Box is definitely on the heap.

Box is owned (as you can see, its - although simplified - declaration in the heading does not contain a generic lifetime parameter), which makes it an ergonomic means of storage for when you do not want to mess with lifetimes and the little extra cost is alright.

Box usage

This is probably the most commonly used pointer types right after borrows. In general, use it wherever you need heap allocation or lifetime magic goes over your head. However, a couple use cases stand out.

Large objects

As Rust by default puts everything on the stack, Box is the simplest suitable means of storage for large objects, such as very large arrays.

This won't work on pretty much any system unless you have increased your system's stack size to a very high value:

fn main() {
    // 1024 * 1024 * 8 bytes
    let _stack_be_gone_ = [0u64; 1024 * 1024];
}

The previous code example will blow your stack, and this might seem fine:

fn main() {
    // 1024 * 1024 * 8 bytes
    let _stack_be_gone_ = Box::new([0u64; 1024 * 1024]);
}

However, the result will be the same, as what this does is create a big array on stack, then move it into the box. The correct solution is rather clunky, and requires some unsafe code:

#![feature(iter_intersperse)]
// const generics come to the rescue!
fn boxed_array<T: Copy, const N: usize>(val: T) -> Box<[T; N]> {
    // first, we need to create an equal Vec, and extract it into a boxed slice, ie. Box<[T]>
    let boxed_slice = vec![val; N].into_boxed_slice();
    // by casting it to a raw pointer, we can then retype it to include the size of the array
    let ptr = Box::into_raw(boxed_slice) as *mut [T; N];
    // of course, creating a box from a raw pointer requires unsafe
    unsafe { Box::from_raw(ptr) }
}

fn main() {
    let heap_chungus: Box<[u64; 1024 * 1024]> = boxed_array(0);
   heap_chungus
       .chunks(1024)
       .map(|row| row
               .iter()
               .map(|n| char::from_digit(*n as u32, 10).unwrap())
               .intersperse(' ')
               .collect::<String>())
       .enumerate()
       .for_each(|(i, line)| println!("{:4}: {}", i, line));
}

Owned trait objects

In the chapter on advanced traits, we took a look at trait objects, however, only under a borrow pointer as &dyn Trait. That is a very lightweight solution and comes in handy, if we want to keep the original object around as a concrete object.

Other times, however, we only care about the trait qualities of a particular object, and Box<dyn Trait>, being an owned value is the most simplest solution.

This can for example be used to have a queue of commands, stored as a vector of trait objects.

use std::fmt::Display;

fn main() {
    // a vec of anything printable really
    let mut v: Vec<Box<dyn Display>> = vec![];

    v.push(Box::new(8));
    v.push(Box::new('c'));
    v.push(Box::new("Hello Braiins"));
    v.push(Box::new(false));
    v.push(Box::new(3.1415));

    for printable in v {
        println!("{}", printable);
    }
}

A boxed trait object is handy for building owned heterogenic collections!

Efficient static length string and collection storage

This is a more niche use-case than the previous ones, but it has been discussed in the Rust community. Sometimes, you might end up with a String or a Vector, which will not be mutated and its length won't change.

A String is essentially a Vec<char> (terms and conditions may apply), and they each store three usizes:

• Pointer
• Length
• Capacity

Turning these into a Box<str> and Box<[T]> respectively essentially strips away the capacity part and makes the value more limited, whether you want this is up to you.

use std::mem;

fn main() {
    println!("{}", mem::size_of::<String>());    // 24
    println!("{}", mem::size_of::<Box<str>>());  // 16
    println!("{}", mem::size_of::<Vec<()>>());   // 24
    println!("{}", mem::size_of::<Box<[()]>>()); // 16
}

8 bytes less is a 1/3 save on what could be stack memory, depending on your use case, however it is only 8 bytes and is well often not worth the hassle.

Recursive data structures

Implementing recursive data-structures and hitting a brick wall doing so has become a common meme in the Rust community, to the point that a book was written exploring the topic as a means of teaching Rust.

The most common pitfall looks roughly like this:

#![allow(unused)]
fn main() {
struct MyList<T> {
    next: Option<MyList<T>>,
    value: T
}
}

This is a type that has infinite size. A similar syntax might work in a different language, where user-defined structures are handled by-reference by default, as is often the case in garbage-collected languages. The Option<T> enum does not introduce indirection either, and has size of size_of::<T>() + 1 (the extra byte denoting presence or lack thereof), so the size of this structure is size_of::<T>() + size_of::<MyList<T>>() + 1, which is obviously recursive, leading to infinity.

If you try to run this code example, rustc helpfully suggests introducing a Box into the fray. Box has a constant size - being a pointer - and thus your structure as a whole now has a resolvable size.

#![allow(unused)]
fn main() {
struct MyList<T> {
    next: Option<Box<MyList<T>>>,
    value: T
}
}

I prefer to keep the Box inside the Option (whereas the error text at the time of this writing suggests the opposite), as it definitely avoids making a heap allocation for an empty Option.

NOTE: As fun fact, if you look at the extended hint for this error (E0072), it basically says "you are trying to implement a linked-list, aren't you? here's how to do it correctly:" ;-)

ANTIPATTERN: Boxed Vec / String

To finish this off, there is actually one thing you shouldn't do, and yet it commonly appears in newbie code.

A newcomer to Rust, but not to the world of more low-level programming, wary of the capacity limitations of the stack, the savvy programmer preemptively puts a vector or a very large string into a Box to avoid filling up the stack.

However, this is actually an anti-pattern as Vec<T> is already on the heap and String is backed by a vector.

clippy already has a lint for this called box_collection.

Per the lints example, this is not to do:

#![allow(unused)]
fn main() {
struct X {
    values: Box<Vec<Foo>>,
}
}

It only adds another level of indirection at no benefit whatsoever and the cost of an extra allocation and needing to go through an extra pointer when accessing your data.

Reference-counted pointer (Rc<T>)

Further moving down the list of Rust's common smart pointers, we got Rc, the reference-counted pointer. Many years ago, a long time before 1.0, Rust used to have a garbage collector, which was later minimized into what was at the time called managed pointers.

These were later removed as a language primitive and Rc<T> was added with the same functionality to the standard library instead.

Rc usage

Reference-counted pointers are much like Box stored on the heap. The major difference is that they keep a counter internally, that tracks how many references there are to the contained object, which literally means how many clones of the Rc still exist undropped.

Once the counter reaches zero, the pointee is dropped as well.

A common newbie mistake is to use Rc<T> as a way around *"I need T: Clone, but my T is not, so I will just wrap it in an Rc<T> which is Clone", but it is still important to know that all copies point to the same object.

As the counter is a plain usize in a Cell, it is not thread-safe and therefore Rc: !Send + !Sync.

#![allow(unused)]
fn main() {
use std::rc::Rc;
use std::ops::Drop;

struct TestStruct;

impl Drop for TestStruct {
    fn drop(&mut self) {
        println!("Even in death, I serve the Omnissiah");
    }
}

fn helper_fn(instance: Rc<TestStruct>) {
    println!("Copy again");
    let copy_of_a_copy_of_a_copy = instance.clone();
    println!("Dropping instance (copy)");
    drop(instance);
    println!("Final instance is dropped here");
}

let test_struct = TestStruct;

// both rc and copy point to the same string
println!("Create Rc, clone it and drop original immediately");
let rc = Rc::new(test_struct).clone(); // so long as we have at least one Rc existing, it won't be dropped
                                       // this creates a clone that will immediately be dropped
println!("Create Copy");
let copy = rc.clone();
println!("Original Rc will be dropped here");
helper_fn(copy);
}

As you can see, the Drop message of TestStruct was only printed once, indicating that no copies of TestStruct have been made.

Self-referential types

Much like Box, Rc is also suitable for self-referential types. Reference-counted pointer in a self-referential type has merit if you need the option of having multiple pointers to the same instance.

Care should be taken not to create an Rc loop that keeps itself alive and leaks memory. Rc supports having a weak reference via the Weak pointer, which is the non-owning counterpart of Rc in that it does not increase the counter and must be upgraded before getting to the data inside, which may return None if the underlying Rc no longer exists due its ref count reaching zero:

#![allow(unused)]
fn main() {
use std::rc::Rc;

let five = Rc::new(5);

let weak_five = Rc::downgrade(&five);

let strong_five: Option<Rc<_>> = weak_five.upgrade();
assert!(strong_five.is_some());

// Destroy all strong pointers.
drop(strong_five);
drop(five);

assert!(weak_five.upgrade().is_none());
}

Example taken from the Weak Rust doc site linked above

Rc<RefCell>

A common pattern of usage of Rc is in conjunction with the RefCell<T> container.

RefCell<T> is a type facilitating interior mutability, which is touched upon above. This allows passing around data that can be mutated even if you only have read-access to the Rc.

#![allow(unused)]
fn main() {
use std::rc::Rc;
use std::cell::RefCell;

let data = Rc::new(RefCell::new(vec![]));
data.borrow_mut().push(42);
println!("{:?}", data.borrow().last());
}

Using Rc is a perfectly appropriate way to sync two 'static parts of your program on one thread. However, things get complicated if we wanted to do this across threads.

Atomic reference-counted pointer (Arc<T>)

That's where the Arc steps in. Just like Rc, it is a reference-counted pointer with pretty much the same behavior, however, the counters in it are atomic, and thus it is safe to use across thread boundary, so Arc: Send + Sync.

Arc usage

Functionally, it is pretty much the equivalent of the Rc, just thread-safe. However, this safety comes at a cost, and Arc is significantly slower than Rc, reportedly, on some systems and platforms, it can be 10-100x slower, but your mileage may vary.

It can also only contain T: Send + Sync, which may seem counter-intuitive, but imagine the situation of someone doing a Arc<Rc<T>> or Arc<RefCell<T>>, these types have non-thread-safe components, and carrying them across the thread boundary could cause trouble.

Sharing state between threads

Just like Rc is ideal for sharing state between two different static parts of your program on a single thread, an Arc is great for sharing data across threads.

#![allow(unused)]
fn main() {
use std::thread;
use std::sync::Arc;

let x = Arc::new(5);
let clone = x.clone();

let thread = thread::spawn(move || {
    println!("clone: {}", clone);
});

println!("main thread: {}", x);
thread.join().unwrap(); // otherwise, we might end earlier before thread gets its turn and its message wouldn't be printed
}

Thread-safe self-referential types

Self-referential types implemented using Rc are not thread-safe, and so they by default will not implement Send and Sync (it's infectious, a single component will prevent these auto-traits from being implemented).

If you want to pass your self-referential structures to other threads, Arc is required.

#![allow(unused)]
fn main() {
use std::sync::Arc;

struct MySelfRef<T> {
    next: Option<Arc<MySelfRef<T>>>,
    value: T,
}

fn are_we_happy<T>(_: T)
where
    T: Send + Sync
{
    println!("Oh, we happy - Vincent Vega");
}

let x = MySelfRef { next: None, value: () };

are_we_happy(x);
}

Arc<Mutex> or Arc<RwLock>

In another parallel with the non-atomic counterpart, the only way to mutate data inside an Arc is by using something that facilitates interior mutability.

As mentioned previously, RefCell<T> is not an option, as it contains non-atomic components.

To this end, Mutex and RwLock are used.

These ensure that only one thread can possibly write into the contained data and that no reads happen in parallel to writes (since data races are one of the common issues safe Rust is guaranteed to prevent).

#![allow(unused)]
fn main() {
use std::thread;
use std::sync::{Arc, Mutex};

let x = Arc::new(Mutex::new(5));
let clone = x.clone();

let thread = thread::spawn(move || {
    let lock = clone.lock().unwrap();
    println!("clone: {}", lock);
    *lock = 12;
});

let lock = x.lock().unwrap();
println!("main thread: {}", lock);
thread.join().unwrap();
}

Depending on luck, that is, which thread wins and gets ahold of a Mutex lock earlier, you might either see main thread print 12 or 5. If you are consistently only getting one result, try using thread::sleep() to tip the balance the other way.

NOTE: It is important to draw a distinction between race conditions and data races. What we created in the previous example is a race condition, not a data race (which is essentially data corruption). Race conditions are not prevented by Rust and they are not considered unsafe, just poor programming.

Clone-on-write pointer (Cow<T>)

The final entry on our list is the oft-forgotten Clone-on-write pointer. This smart pointer encloses and provides immutable access to borrowed data, and clones the data lazily when mutation or ownership is required.

It works with any borrowed data, so long as it implements the ToOwned trait, which generally comes in tandem with Borrow.

Cow usage

Cow<T> is best utilized on data, which are unlikely to change in most cases, if we then use cow with some constant, static or a literal, we can save resources of needless allocations and constructions of owned values, which are generally necessary for any sort of data mutations.

It is important to know that Cow isn't fully owned, and it contains a lifetime in its definition, fully written as Cow<'a, B> (B for Borrowed).

Avoiding allocation when storing either a string literal or dynamic string (Cow<'static, str>)

A lot of the usage of Cow revolves around strings. One common use case is having many strings, which may mostly be a literal, that is &'static str, but sometimes may be a dynamically procured string, which in all likelihood is of type String. Cow helps here prevent creating a String (which involves an allocation) for all of the cases where we would use the literal

Efficient storage for borrowed strings unlikely to mutate

#![allow(unused)]
fn main() {
let some_str = "hello";
let s = Cow::Borrowed(some_str);
}

This is a similar scenario, only for non-static borrowed strings.

The benefits of Cow are perhaps best explained by Pascal Hertleif in his post from 2018 titled "The Secret Life of Cows"

The Task - A multi-threaded reverse polish notation calculator

A reverse-polish notation calculator is a calculator, which uses the operands-then-operator syntax, for example, the expression 2 + 7 * 4 would be written as:

2 7 4 * +

You can see more about the syntax here https://en.wikipedia.org/wiki/Reverse_Polish_notation.

The major benefit of this is that you don't need parenthesis and you can handle your operands as a stack data structure.

In this project, the goal is to implement a multi-threaded calculator using this, where:

• one thread handles input and fills a queue of command
• one thread processes the commands periodically
• and the last thread periodically prints the content of the stack/memory, so we can see the results of our math.

To do this, we will use trait objects and appropriate pointer types.

1. Input reading

Let's start with the input thread.

In the main function, create a loop which reads a line of input, converts it into the appropriate string type, if necessary, then cuts it up into the tokens.

From an input like this:

2 7 4 * + 3 -

You should be able to get the tokens [2, 7, 4, *, +, 3, -]. To ensure you got it correctly, you can print them to stdout.

2. Input parsing

Create a structure for each of the following operations:

• insertion (a number literal)
• addition (+)
• subtraction (-)
• multiplication (*)
• division (/)
• exit (q)

Next create a trait Command, which looks a bit like this:

#![allow(unused)]
fn main() {
pub trait Command {
    fn execute(&self, stack: <...some way to mutably access a Vec<i64>...>);
}
}

And implement it accordingly for each of the structures. If the operation is invalid (perhaps because there is not enough numbers on the stack), consider it a no-op.

You can extend or modify this trait, however, make sure it remains object-safe so you can make trait-objects out of it.

3. Shared state and other threads

In your main thread, spin up two more threads.

Also create a structure for your State, which should contain the following:

• The stack, which should be a list of i64
• A queue of commands, which should be a list of dyn Command

Both may be wrapped pointers and/or containers, and that applies to the contents of these lists as well. Refer to the text above to make appropriate choices in this matter.

Now, add two constants to your program:

• PRINT_INTERVAL - a duration of how long between prints, set to 15s
• ÈVAL_INTERVAL - a duration of how long before the executing thread next tries to go through the queue of the Commands, set to 10s

Lastly, create an instance of your state in main(), wrapped appropriately into the correct smart pointer and perhaps container.

4. Putting it all together

Share your instance between all three threads, and implement functionality such that:

• Input thread parses text input into the correct T: Command structures and inserts them as trait objects into the queue in state
• Worker thread pops off commands from the queue and executes them, modifying the stack in the process every EVAL_INTERVAL
• Print thread prints the contents of the stack every PRINT_INTERVAL

For development, you can of course adjust the length of these intervals

5. End product

In the end you should be left with a well prepared project, that has the following:

• documented code explaining your reasoning where it isn't self-evident
• optionally tests
• and an example or two where applicable
• clean git history that does not contain fix-ups, merge commits or malformed/misformatted commits

Your Rust code should be formatted by rustfmt / cargo fmt and should produce no warnings when built. It should also work on stable Rust and follow the Braiins Standard