tagged-pointer

This crate provides an implementation of tagged pointers: a space-efficient representation of a pointer and integer tag. In particular, both TaggedPtr and Option<TaggedPtr> are the size of a pointer despite containing both a pointer and tag.

This crate depends only on core, so it can be used in no_std environments.

Example

use core::mem::size_of;
use core::ptr::NonNull;
use tagged_pointer::TaggedPtr;

#[repr(align(4))]
struct Item(u32, u32);

// `TaggedPtr` and `Option<TaggedPtr>` are both the size of a pointer:
assert_eq!(size_of::<TaggedPtr<Item, 2>>(), size_of::<*mut ()>());
assert_eq!(size_of::<Option<TaggedPtr<Item, 2>>>(), size_of::<*mut ()>());

let item1 = Item(1, 2);
let item2 = Item(3, 4);

// We can store two bits of the tag, since `Item` has an alignment of 4.
let tp1 = TaggedPtr::<_, 2>::new(NonNull::from(&item1), 1);
let tp2 = TaggedPtr::<_, 2>::new(NonNull::from(&item2), 3);

let (ptr1, tag1) = tp1.get();
let (ptr2, tag2) = tp2.get();

assert_eq!((ptr1, tag1), (NonNull::from(&item1), 1));
assert_eq!((ptr2, tag2), (NonNull::from(&item2), 3));

Platform considerations

The number of tag bits that can be stored in a pointer of a given type depends on the type’s alignment. However, the alignment of many types is platform-specific: u64, for example, could have an alignment of 8 on one platform and 4 on another.

Therefore, it is highly recommended to use #[repr(align)] to guarantee a minimum alignment, defining a wrapper type if necessary:

// This won't work on systems where `u64` has an alignment of 4!
let x: u64 = 123;
let tp = TaggedPtr::<u64, 3>::new(NonNull::from(&x), 0b11);

// Instead, do this:
#[repr(align(8))]
struct MyU64(pub u64);

let x = MyU64(123);
let tp = TaggedPtr::<MyU64, 3>::new(NonNull::from(&x), 0b11);

Assumptions

This crate avoids making assumptions about the representations of pointers. In particular, it does not cast pointers to usize and assume that the lower bits of that number can be used for tagging. There exist architectures that do not allow reusing the lower bits of aligned pointers in this manner, and even if none are currently supported by Rust, that could change in the future. This crate’s approach also works better with strict provenance.

Previously, this crate relied on assumptions about the behavior of pointer::align_offset in certain circumstances. These assumptions were effectively always true, but were not strictly guaranteed, so a fallback implementation was provided with the crate feature fallback, which would avoid relying on this assumption at the cost of space efficiency.

However, as of Rust 1.78, this assumption is no longer necessary: align_offset is guaranteed to behave as required.

Documentation

Documentation is available on docs.rs.

License

tagged-pointer is licensed under version 2 of the Apache License. See LICENSE.

Contributing

By contributing to tagged-pointer, you agree that your contribution may be used according to the terms of tagged-pointer’s license.