Mainstream programming languages use one or more of the following approaches (if any) to achieve memory safety:

• Tracing Garbage Collection (GC for short)

• Reference Counting (RC for short)

• Linear/Affine Types (RAII + std::unique_ptr is similar)

• “Borrow Checking” (i.e., Static Lifetime Analysis)

Each solution has different tradeoffs: GC requires a hefty and complex runtime to be both global and efficient; RC can’t handle cycles and has some performance overhead to track the reference counts; Linear/Affine Types/RAII impose a tree-like structure to memory; Borrow Checking is insufficient by itself and imposes quite a few constraints that can be hard to understand (so called “fighting the borrow checker”)

But there is actually one more approach that could be used: Pointer Tagging. Often discussed in the context of hardware solutions like CHERI, pointer tagging can also be implemented in software with a reasonable performance cost.

The basic idea is to add some extra tag bits to a pointer such that we can determine if the memory address it points to is still valid. If the tag bits in the pointer and the tag bits of the allocation don’t match, then the data at that memory address has been freed and overwritten, and we have therefore caught a Use-After-Free.

But how do we produce and manage these tag bits? Read on.

The idea of pointer tagging is similar to a common approach to track slot reuse in object pools: generational handles.

When you add an object to a pool, you get back a handle: an index to the slot where that object is stored. You can use this handle to grab the corresponding object and work with it. But what happens if the object has been freed and a new object was added to the same slot in the pool? How do you know if the handle remains valid?

The simple solution is to track the “generation” of the object in the slot. Whenever an object in a slot is deleted, that slot’s generation counter is incremented, so the next object placed at that slot has a higher generation count.

Instead of returning just an index as a handle, the pool returns an index + generation pair. When accessing a slot using a handle, its generation value is compared to the generation value of the slot. If they don’t match, the handle is no longer valid.

If generation counts are allowed to wrap around, then “generation collisions” become possible, but such collisions are extremely unlikely given enough bits for the generation counter.

To give some perspective, if you do nothing but increment a 64 bit number every clock cycle on a 3 GHz CPU, it will take 97 years to overflow.

Generational References, a term coined by the developer of the Vale programming language, extend the idea of Generational Handles to arbitrary pointers. They’re a form of pointer tagging inspired by generational handles, hence the name.

An implementation similar to the approach used for generational handles requires a custom memory allocator since we need to manage the generation counts separately from the allocations. But there’s another really clever solution that was implemented in Vale that avoids this issue, remaining compatible with malloc, and it is the one we’ll use: random tags.

We’ll implement Tagged Pointers / Generational References in C++ using a smart pointer class we’ll call tag_ptr. These smart pointers don’t actually do any memory management themselves, like std::unique_ptr or std::shared_ptr, they only provide memory safety.

The idea is as follows: A simple thread-local random number generator is used to produce a stream of 64 bit numbers to use as tags.

A function make_tagged allo