Tagged pointers and object headers

Since our virtual machine will support a dynamic language where the compiler does no type checking, all the type information will be managed at runtime.

In the previous chapter, we introduced a pointer type ScopedPtr<T>. This pointer type has compile time knowledge of the type it is pointing at.

We need an alternative to ScopedPtr<T> that can represent all the runtime-visible types so they can be resolved at runtime.

As we'll see, carrying around type information or looking it up in the header on every access will be inefficient space and performance-wise.

We'll implement a common optimization: tagged pointers.

Runtime type identification

The object header can always give us the type id for an object, given a pointer to the object. However, it requires us to do some arithmetic on the pointer to get the location of the type identifier, then dereference the pointer to get the type id value. This dereference can be expensive if the object being pointed at is not in the CPU cache. Since getting an object type is a very common operation in a dynamic language, these lookups become expensive, time-wise.

Rust itself doesn't have runtime type identification but does have runtime dispatch through trait objects. In this scheme a pointer consists of two words: the pointer to the object itself and a second pointer to the vtable where the concrete object type's methods can be looked up. The generic name for this form of pointer is a fat pointer.

We could easily use a fat pointer type for runtime type identification in our interpreter. Each pointer could carry with it an additional word with the type id in it, or we could even just use trait objects!

A dynamically typed language will manage many pointers that must be type identified at runtime. Carrying around an extra word per pointer is expensive, space-wise, however.

Tagged pointers

Many runtimes implement tagged pointers to avoid the space overhead, while partially improving the time overhead of the header type-id lookup.

In a pointer to any object on the heap, the least most significant bits turn out to always be zero due to word or double-word alignment.

On a 64 bit platform, a pointer is a 64 bit word. Since objects are at least word-aligned, a pointer is always be a multiple of 8 and the 3 least significant bits are always 0. On 32 bit platforms, the 2 least significant bits are always 0.

  64..............48..............32..............16...........xxx
0b1111111111111111111111111111111111111111111111111111111111111000
                                                               / |
                                                              /  |
                                                            unused

When dereferencing a pointer, these bits must always be zero. But we can use them in pointers at rest to store a limited type identifier! We'll limit ourselves to 2 bits of type identifier so as to not complicate our code in distinguishing between 32 and 64 bit platforms¹.

Given we'll only have 4 possible types we can id directly from a pointer, we'll still need to fall back on the object header for types that don't fit into this range.

Encoding this in Rust

Flipping bits on a pointer directly definitely constitutes a big Unsafe. We'll need to make a tagged pointer type that will fundamentally be unsafe because it won't be safe to dereference it. Then we'll need a safe abstraction over that type to make it safe to dereference.

But first we need to understand the object header and how we get an object's type from it.

The object header

We introduced the object header traits in the earlier chapter Defining the allocation API. The chapter explained how the object header is the responsibility of the interpreter to implement.

Now that we need to implement type identification, we need the object header.

The allocator API requires that the type identifier implement the AllocTypeId trait. We'll use an enum to identify for all our runtime types:

#[repr(u16)]
#[derive(Debug, Copy, Clone, PartialEq)]
pub enum TypeList {
    ArrayBackingBytes,
    ArrayOpcode,
    ArrayU8,
    ArrayU16,
    ArrayU32,
    ByteCode,
    CallFrameList,
    Dict,
    Function,
    InstructionStream,
    List,
    NumberObject,
    Pair,
    Partial,
    Symbol,
    Text,
    Thread,
    Upvalue,
}

// Mark this as a Stickyimmix type-identifier type
impl AllocTypeId for TypeList {}

Given that the allocator API requires every object that can be allocated to have an associated type id const, this enum represents every type that can be allocated and that we will go on to describe in this book.

It is a member of the ObjectHeader struct along with a few other members that our Immix implementation requires:

pub struct ObjectHeader {
    mark: Mark,
    size_class: SizeClass,
    type_id: TypeList,
    size_bytes: u32,
}

The rest of the header members will be the topic of the later garbage collection part of the book.

A safe pointer abstraction

A type that can represent one of multiple types at runtime is obviously the enum. We can wrap possible ScopedPtr<T> types like so:

#[derive(Copy, Clone)]
pub enum Value<'guard> {
    ArrayU8(ScopedPtr<'guard, ArrayU8>),
    ArrayU16(ScopedPtr<'guard, ArrayU16>),
    ArrayU32(ScopedPtr<'guard, ArrayU32>),
    Dict(ScopedPtr<'guard, Dict>),
    Function(ScopedPtr<'guard, Function>),
    List(ScopedPtr<'guard, List>),
    Nil,
    Number(isize),
    NumberObject(ScopedPtr<'guard, NumberObject>),
    Pair(ScopedPtr<'guard, Pair>),
    Partial(ScopedPtr<'guard, Partial>),
    Symbol(ScopedPtr<'guard, Symbol>),
    Text(ScopedPtr<'guard, Text>),
    Upvalue(ScopedPtr<'guard, Upvalue>),
}

Note that this definition does not include all the same types that were listed above in TypeList. Only the types that can be passed dynamically at runtime need to be represented here. The types not included here are always referenced directly by ScopedPtr<T> and are therefore known types at compile and run time.

You probably also noticed that Value is the fat pointer we discussed earlier. It is composed of a set of ScopedPtr<T>s, each of which should only require a single word, and an enum discriminant integer, which will also, due to alignment, require a word.

This enum, since it wraps ScopedPtr<T> and has the same requirement for an explicit lifetime, is Safe To Dereference.

As this type occupies the same space as a fat pointer, it isn't the type we want for storing pointers at rest, though. For that type, let's look at the compact tagged pointer type now.

What lies beneath

Below we have a union type, making this an unsafe representation of a pointer. The tag value will be constrained to the values 0, 1, 2 or 3, which will determine which of the next four possible members should be accessed. Members will have to be bit-masked to access their correct values.

#[derive(Copy, Clone)]
pub union TaggedPtr {
    tag: usize,
    number: isize,
    symbol: NonNull<Symbol>,
    pair: NonNull<Pair>,
    object: NonNull<()>,
}

As you can see, we've allocated a tag for a Symbol type, a Pair type and one for a numeric type. The fourth member indicates an object whose type must be determined from the type id in the object header.

Note: Making space for an inline integer is a common use of a tag. It means any integer arithmetic that fits within the available bits will not require memory lookups into the heap to retrieve operands. In our case we've defined the numeric type as an isize. Since the 2 least significant bits are used for the tag, we will have to right-shift the value by 2 to extract the correct integer value. We'll go into this implementation in more depth in a later chapter.

The tags and masks are defined as:

const TAG_MASK: usize = 0x3;
pub const TAG_SYMBOL: usize = 0x0;
pub const TAG_PAIR: usize = 0x1;
pub const TAG_OBJECT: usize = 0x2;
pub const TAG_NUMBER: usize = 0x3;
const PTR_MASK: usize = !0x3;

Thus you can see from the choice of embedded tag values, we've optimized for fast identification of Pairs and Symbols and integer math. If we decide to, it will be easy to switch to other types to represent in the 2 tag bits.

Connecting into the allocation API

Translating between Value and TaggedPtr will be made easier by creating an intermediate type that represents all types as an enum but doesn't require a valid lifetime. This type will be useful because it is most closely ergonomic with the allocator API and the object header type information.

#[derive(Copy, Clone)]
pub enum FatPtr {
    ArrayU8(RawPtr<ArrayU8>),
    ArrayU16(RawPtr<ArrayU16>),
    ArrayU32(RawPtr<ArrayU32>),
    Dict(RawPtr<Dict>),
    Function(RawPtr<Function>),
    List(RawPtr<List>),
    Nil,
    Number(isize),
    NumberObject(RawPtr<NumberObject>),
    Pair(RawPtr<Pair>),
    Partial(RawPtr<Partial>),
    Symbol(RawPtr<Symbol>),
    Text(RawPtr<Text>),
    Upvalue(RawPtr<Upvalue>),
}

We'll extend Heap (see previous chapter) with a method to return a tagged pointer on request:

impl Heap {
    fn alloc_tagged<T>(&self, object: T) -> Result<TaggedPtr, RuntimeError>
    where
        FatPtr: From<RawPtr<T>>,
        T: AllocObject<TypeList>,
    {
        Ok(TaggedPtr::from(FatPtr::from(self.heap.alloc(object)?)))
    }
}

In this method it's clear that we implemented From<T> to convert between pointer types. Next we'll look at how these conversions are implemented.

Type conversions

We have three pointer types: Value, FatPtr and TaggedPtr, each which has a distinct flavor. We need to be able to convert from one to the other:

TaggedPtr <-> FatPtr -> Value

FatPtr to Value

We can implement From<FatPtr> for TaggedPtr and Value to convert to the final two possible pointer representations. Well, not exactly - the function signature

impl From<FatPtr> for Value<'guard> {
    fn from(ptr: FatPtr) -> Value<'guard> { ... }
}

is not able to define the 'guard lifetime, so we have to implement a similar method that can:

impl FatPtr {
    pub fn as_value<'guard>(&self, guard: &'guard dyn MutatorScope) -> Value<'guard> {
        match self {
            FatPtr::ArrayU8(raw_ptr) => {
                Value::ArrayU8(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard)))
            }
            FatPtr::ArrayU16(raw_ptr) => {
                Value::ArrayU16(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard)))
            }
            FatPtr::ArrayU32(raw_ptr) => {
                Value::ArrayU32(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard)))
            }
            FatPtr::Dict(raw_ptr) => Value::Dict(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard))),
            FatPtr::Function(raw_ptr) => {
                Value::Function(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard)))
            }
            FatPtr::List(raw_ptr) => Value::List(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard))),
            FatPtr::Nil => Value::Nil,
            FatPtr::Number(num) => Value::Number(*num),
            FatPtr::NumberObject(raw_ptr) => {
                Value::NumberObject(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard)))
            }
            FatPtr::Pair(raw_ptr) => Value::Pair(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard))),
            FatPtr::Partial(raw_ptr) => {
                Value::Partial(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard)))
            }
            FatPtr::Symbol(raw_ptr) => {
                Value::Symbol(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard)))
            }
            FatPtr::Text(raw_ptr) => Value::Text(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard))),
            FatPtr::Upvalue(raw_ptr) => {
                Value::Upvalue(ScopedPtr::new(guard, raw_ptr.scoped_ref(guard)))
            }
        }
    }
}

FatPtr to TaggedPtr

For converting down to a single-word TaggedPtr type we will introduce a helper trait and methods to work with tag values and RawPtr<T> types from the allocator:

pub trait Tagged<T> {
    fn tag(self, tag: usize) -> NonNull<T>;
    fn untag(from: NonNull<T>) -> RawPtr<T>;
}

impl<T> Tagged<T> for RawPtr<T> {
    fn tag(self, tag: usize) -> NonNull<T> {
        unsafe { NonNull::new_unchecked((self.as_word() | tag) as *mut T) }
    }

    fn untag(from: NonNull<T>) -> RawPtr<T> {
        RawPtr::new((from.as_ptr() as usize & PTR_MASK) as *const T)
    }
}

This will help convert from RawPtr<T> values in FatPtr to the NonNull<T> based TaggedPtr discriminants.

Because TaggedPtr is a union type and because it has to apply the appropriate tag value inside the pointer itself, we can't work with it as ergnomically as an enum. We'll create some more helper functions for instantiating TaggedPtrs appropriately.

Remember that for storing an integer in the pointer we have to left-shift it 2 bits to allow for the tag. We'll apply proper range checking in a later chapter.

impl TaggedPtr {
    pub fn nil() -> TaggedPtr {
        TaggedPtr { tag: 0 }
    }

    pub fn number(value: isize) -> TaggedPtr {
        TaggedPtr {
            number: (((value as usize) << 2) | TAG_NUMBER) as isize,
        }
    }

    pub fn symbol(ptr: RawPtr<Symbol>) -> TaggedPtr {
        TaggedPtr {
            symbol: ptr.tag(TAG_SYMBOL),
        }
    }

    fn pair(ptr: RawPtr<Pair>) -> TaggedPtr {
        TaggedPtr {
            pair: ptr.tag(TAG_PAIR),
        }
    }
}

Finally, we can use the above methods to implement From<FatPtr for TaggedPtr:

impl From<FatPtr> for TaggedPtr {
    fn from(ptr: FatPtr) -> TaggedPtr {
        match ptr {
            FatPtr::ArrayU8(raw) => TaggedPtr::object(raw),
            FatPtr::ArrayU16(raw) => TaggedPtr::object(raw),
            FatPtr::ArrayU32(raw) => TaggedPtr::object(raw),
            FatPtr::Dict(raw) => TaggedPtr::object(raw),
            FatPtr::Function(raw) => TaggedPtr::object(raw),
            FatPtr::List(raw) => TaggedPtr::object(raw),
            FatPtr::Nil => TaggedPtr::nil(),
            FatPtr::Number(value) => TaggedPtr::number(value),
            FatPtr::NumberObject(raw) => TaggedPtr::object(raw),
            FatPtr::Pair(raw) => TaggedPtr::pair(raw),
            FatPtr::Partial(raw) => TaggedPtr::object(raw),
            FatPtr::Text(raw) => TaggedPtr::object(raw),
            FatPtr::Symbol(raw) => TaggedPtr::symbol(raw),
            FatPtr::Upvalue(raw) => TaggedPtr::object(raw),
        }
    }
}

TaggedPtr to FatPtr

To convert from a TaggedPtr to the intermediate type is implemented in two parts: identifying object types from the tag; identifying object types from the header where the tag is insufficient.

Part the first, which requires unsafe due to accessing a union type and dereferencing the object header for the TAG_OBJECT discriminant:

impl From<TaggedPtr> for FatPtr {
    fn from(ptr: TaggedPtr) -> FatPtr {
        ptr.into_fat_ptr()
    }
}

impl TaggedPtr {
    fn into_fat_ptr(&self) -> FatPtr {
        unsafe {
            if self.tag == 0 {
                FatPtr::Nil
            } else {
                match get_tag(self.tag) {
                    TAG_NUMBER => FatPtr::Number(self.number >> 2),
                    TAG_SYMBOL => FatPtr::Symbol(RawPtr::untag(self.symbol)),
                    TAG_PAIR => FatPtr::Pair(RawPtr::untag(self.pair)),

                    TAG_OBJECT => {
                        let untyped_object_ptr = RawPtr::untag(self.object).as_untyped();
                        let header_ptr = HeapStorage::get_header(untyped_object_ptr);

                        header_ptr.as_ref().get_object_fatptr()
                    }

                    _ => panic!("Invalid TaggedPtr type tag!"),
                }
            }
        }
    }
}

And part two, the object header method get_object_fatptr() as seen in the code above:

impl ObjectHeader {
    pub unsafe fn get_object_fatptr(&self) -> FatPtr {
        let ptr_to_self = self.non_null_ptr();
        let object_addr = HeapStorage::get_object(ptr_to_self);

        match self.type_id {
            TypeList::ArrayU8 => FatPtr::ArrayU8(RawPtr::untag(object_addr.cast::<ArrayU8>())),
            TypeList::ArrayU16 => FatPtr::ArrayU16(RawPtr::untag(object_addr.cast::<ArrayU16>())),
            TypeList::ArrayU32 => FatPtr::ArrayU32(RawPtr::untag(object_addr.cast::<ArrayU32>())),
            TypeList::Dict => FatPtr::Dict(RawPtr::untag(object_addr.cast::<Dict>())),
            TypeList::Function => FatPtr::Function(RawPtr::untag(object_addr.cast::<Function>())),
            TypeList::List => FatPtr::List(RawPtr::untag(object_addr.cast::<List>())),
            TypeList::NumberObject => {
                FatPtr::NumberObject(RawPtr::untag(object_addr.cast::<NumberObject>()))
            }
            TypeList::Pair => FatPtr::Pair(RawPtr::untag(object_addr.cast::<Pair>())),
            TypeList::Partial => FatPtr::Partial(RawPtr::untag(object_addr.cast::<Partial>())),
            TypeList::Symbol => FatPtr::Symbol(RawPtr::untag(object_addr.cast::<Symbol>())),
            TypeList::Text => FatPtr::Text(RawPtr::untag(object_addr.cast::<Text>())),
            TypeList::Upvalue => FatPtr::Upvalue(RawPtr::untag(object_addr.cast::<Upvalue>())),

            // Other types not represented by FatPtr are an error to id here
            _ => panic!("Invalid ObjectHeader type tag {:?}!", self.type_id),
        }
    }
}

This method contains no unsafe code and yet we've declared it unsafe!

Manipulating pointer types is not unsafe in of itself, only dereferencing them is unsafe and we are not dereferencing them here.

While we have the safety rails of the enum types to prevent invalid types from being returned, we could easily mismatch a TypeList value with an incorrect FatPtr value and return an incorrect type. Additionally we could forget to untag a pointer, leaving it as an invalid pointer value.

These possible mistakes could cause undefined behavior and quite likely crash the interpreter.

The compiler will not catch these cases and so this is an area for critical scrutiny of correctness! Hence the method is marked unsafe to draw attention.

Using tagged pointers in data structures

Finally, we need to see how to use these types in data structures that we'll create.

In the previous chapter, we defined a CellPtr type that wrapped a RawPtr<T> in a Cell<T> so that data structures can contain mutable pointers to other objects. Similarly, we'll want something to wrap tagged pointers:

#[derive(Clone)]
pub struct TaggedCellPtr {
    inner: Cell<TaggedPtr>,
}

We'll also wrap Value in a type TaggedScopedPtr that we'll use similarly to ScopedPtr<T>.

#[derive(Copy, Clone)]
pub struct TaggedScopedPtr<'guard> {
    ptr: TaggedPtr,
    value: Value<'guard>,
}

This TaggedScopedPtr carries an instance of TaggedPtr and a Value. This tradeoff means that while this type has three words to heft around, the TaggedPtr member can be quickly accessed for copying into a TaggedCellPtr without needing to down-convert from Value.

The type is only suitable for handling pointers that actively need to be dereferenced due to it's size.

Note: Redundancy: TaggedScopedPtr and Value are almost identical in requirement and functionality. TODO: consider merging into one type. See issue https://github.com/rust-hosted-langs/book/issues/30

A TaggedScopedPtr can be obtained by:

• calling TaggedCellPtr::get()
• or the MutatorView::alloc_tagged() method

The get() method on TaggedCellPtr returns a TaggedScopedPtr:

impl TaggedCellPtr {
    pub fn get<'guard>(&self, guard: &'guard dyn MutatorScope) -> TaggedScopedPtr<'guard> {
        TaggedScopedPtr::new(guard, self.inner.get())
    }
}

The MutatorView method to allocate a new object and get back a tagged pointer (a TaggedScopedPtr) looks simply like this:

impl MutatorView {
    pub fn alloc_tagged<T>(&self, object: T) -> Result<TaggedScopedPtr<'_>, RuntimeError>
    where
        FatPtr: From<RawPtr<T>>,
        T: AllocObject<TypeList>,
    {
        Ok(TaggedScopedPtr::new(self, self.heap.alloc_tagged(object)?))
    }
}

Quick recap

In summary, what we created here was a set of pointer types:

• types suitable for storing a pointer at rest - TaggedPtr and TaggedCellPtr
• types suitable for dereferencing a pointer - Value and TaggedScopedPtr
• a type suitable for intermediating between the two - FatPtr - that the heap allocation interface can return

We now have the basic pieces to start defining data structures for our interpreter, so that is what we shall do next!