Pointers in Rust: Whacking the Mole (Part 1)

What will you learn:

How pointers create pitfalls for a number of hard-to-detect programming errors.
How Rust avoids these pitfalls and catches most pointer errors at compile time.

Pointers have been a staple of programming languages since the earliest days of computing, serving two purposes:

Indirection: A means to share (rather than copy) data values within a program. This can be implicit, for example by passing a variable as a “by reference” parameter, or explicit through syntax for reference creating/dereferencing (such as “&x” and “*p” in C).
Dynamic allocation: a means to construct and manipulate data structures (linked lists, trees, graphs, …) that can grow and shrink during program execution.

However, with power comes danger, and pointers can compromise both safety and performance in mission-critical systems.

This article will summarize the challenges that pointers bring and explain how Rust meets these challenges. Rust’s approach requires programmers to think about pointers in a new way, but the effect is memory safety/early detection of pointer errors and efficient performance, with the expressiveness of a general-purpose data-structuring facility.

Indirection Issues with C

Allowing a pointer to outlive the value it points to creates an insidious bug known as a dangling reference. For example, if a C function returns a reference to one of its local variables and then accesses the value referenced by the function’s result, the effect is undefined. The error can be hard to diagnose, since any anomalous behavior is manifest not when the dangling reference is created, but instead at some later point when the invalid value is used.

Unprotected access to a value shared across multiple threads (a “data race”) is equally dangerous. Without some protection ensuring mutual exclusion, the value can be corrupted if it’s being assigned by one thread while being either assigned or read by another thread.

And as with dangling references, the effect isn’t necessarily localized to the construct where the error occurs. Debugging concurrent code is challenging in general because of the multiple possible control paths; data races raise the ante considerably.

Performance can also take a hit, since indirect accesses complicate the analysis needed for optimizations. Aliasing in the following C program illustrates the problem:

#include <stdio.h> 

int func(const int *p, int *q){ 
   (*q)++; 
   return *p + *p; 
} 

void main(){ 
   int n = 100; 
   printf("func() returns %d\n", func(&n, &n)); // 202 
}

An optimizing compiler would like to store *p in a register on entry to func(), for use in the return statement. However, this would require the (invalid) assumption that *p and *q don’t overlap.

Dynamic Allocation Issues

Many applications require data structures whose size can grow and shrink dynamically, with no a priori limit on the maximum size. Programming languages accommodate this requirement through dynamic allocation in a storage area known as the heap. However, that raises the issue of when and how to reclaim storage that’s no longer accessible (so-called “garbage”).

Solutions fall roughly into three main categories, each with pros and cons:

Manual Deallocation

Languages like C, C++, and Ada allow for the programmer to free memory that the program has explicitly allocated. This “trust the programmer” philosophy runs the risk of storage leakage (if the programmer forgets to deallocate), dangling references (if the storage is deallocated while still being referenced), double freeing (deallocating the same storage more than once), and heap fragmentation (insufficient contiguous space for an allocation).

Variations on this approach let the programmer define memory pools, where each allocation for the same pointer type uses storage in a specific fixed-size area. If all objects in a pool have the same size, this can prevent fragmentation and enable constant-time allocation and deallocation. Further, the entire pool for a locally declared pointer type can be reclaimed at once at scope exit.

The manual deallocation approach is efficient but error-prone. Deciding when it’s safe to free a pointer can entail complicated analysis, and predicting an appropriate size for a memory pool can likewise be difficult.

Manual deallocation doesn’t help if a data structure is implicitly allocated on the heap by the compiled code. In such cases, the compiler vendor’s run-time support library is responsible for freeing the storage when it’s safe to do so.

Automatic Deallocation

Languages like Java and Python don’t allow the programmer to explicitly free storage. Instead, they provide a run-time service known as a garbage collector to automatically deallocate inaccessible values.

Garbage collection has been the subject of research since the 1960s and can be implemented through a wide range of techniques. Some are incremental, incurring an overhead in time and/or space that is distributed across program execution, while others use “stop the world” algorithms that kick in and reclaim garbage when the available heap space gets below a specific threshold.

Garbage collection prevents deallocation-related bugs and avoids storage leakage from inaccessible values, and some techniques can also prevent heap fragmentation. However, algorithmic complexity as well as time and/or space expense have made garbage collection impractical for critical real-time software. The garbage collection approach is safe (assuming that it’s implemented correctly), but it incurs a penalty in performance and predictability.

Semi-automatic Deallocation

Complementing their support for manual deallocation, languages like C++ and Ada enable the programmer to define special functions, on a per-type basis, that are invoked at specific points in program execution where storage management may be affected. Common “hook” points are assignment, parameter passing, and scope exit. The functions can be defined to implement basic reclamation strategies such as reference counting.

Semi-automatic deallocation can effectively support storage reclamation for non-cyclic data structures, with better time and space predictability than for general garbage collection. It’s also preferable methodologically to manual deallocation, since it places the responsibility for resource cleanup on the implementer of the resource rather than on the user. The approach is safe and can be implemented efficiently, but it doesn’t scale up to complex data structures.

The “Billion-Dollar Mistake”: The Null Pointer

A related issue is the semantics for uninitialized pointers. Languages typically provide a special “null” value as a solution—a pointer that doesn’t reference any value.

In some languages (e.g., Ada and Java), the null value is used as the default initialization for pointers, and attempting to dereference a null pointer raises a run-time exception. Other languages (e.g., C and C++) treat such attempts as undefined behavior. In either case, it’s a program error, and bugs related to null pointers have infected programs for decades.

At the 2009 QCon conference in London, Prof. Anthony Hoare took responsibility for introducing null pointers in ALGOL W back in 1964, and thereby creating what he called “my billion-dollar mistake.” That number has since gone up considerably. Evidence points to (pardon the pun) a NULL dereference from C++ code, in a file incorrectly installed as part of a CrowdStrike software update, as the trigger for the Windows crash that crippled enterprise IT systems worldwide in late July 2024.

The Pointer Mole

All of this presents a dilemma for language designers, compiler writers, and software developers, especially in application areas demanding high assurance, run-time efficiency, and space/time predictability. In some situations, it’s preferable to avoid the problem rather than attempt a solution.

As an example, coding standards for software that needs to be certified under rigorous assurance standards typically restrict dynamic allocation to the initialization/startup code and disallow deallocation. With these limitations, the software will not exhaust heap storage and will not suffer dangling references. However, the restrictions don’t prevent concurrency-related pointer errors on accesses to shared data, and they require analysis to ensure no dereferencing of null pointers.

There are no perfect solutions, and to a software developer it may seem like a frustrating game of “Whack-A-Mole.” If you want a pointer facility that’s expressive, safe, and efficient, then pick two; the third will be elusive.

Expressive and safe? Try Java, but be prepared to sacrifice performance. Expressive and efficient? Welcome to C and C++, but realize that safety requires painstaking effort and comes in spite of, rather than because of, pointer semantics. Safe and efficient? The SPARK subset of Ada fills the bill, but with a subset of typical pointer functionality.

The full Ada language comes close to meeting all three goals, but its null pointers repeat Prof. Hoare’s billion-dollar mistake. The pesky pointer mole seems impervious to destruction.