noratrieb / stuff

stuffing things into pointers in a strict provenance friendly way

stuff

A crate for stuffing things into a pointer.

This crate is tested using miri (with -Zmiri-tag-raw-pointers).

stuff helps you to

• Stuff arbitrary data into pointers
• Stuff pointers or arbitrary data into fixed size storage (u64, u128)

in a portable and provenance friendly way.

It does by providing an abstraction around it, completely abstracting away the provenance and pointers from the user, allowing the user to do their bit stuffing only on integers (pointer addresses) themselves.

StuffedPtr is the main type of this crate. It's a type whose size depends on the choice of Backend (defaults to usize, u64 and u128 are also possible). It can store a pointer or some other data.

You can choose any arbitrary bitstuffing depending on the StuffingStrategy, a trait that governs how the other data (or the pointer itself) will be packed into the backend.

Example: NaN-Boxing

Pointers are hidden in the NaN values of floats. NaN boxing often involves also hiding booleans or null in there, but we stay with floats and pointers (pointers to a HashMap that servers as our "object" type).

See crafting interpreters for more details.

use std::collections::HashMap;
use std::convert::{TryFrom, TryInto};
use std::mem::ManuallyDrop;

use stuff::{StuffedPtr, StuffingStrategy, Unstuffed};

// Create a unit struct for our strategy
struct NanBoxStrategy;

// implementation detail of NaN boxing, a quiet NaN mask
const QNAN: u64 = 0x7ffc000000000000;
// implementation detail of NaN boxing, the sign bit of an f64
const SIGN_BIT: u64 = 0x8000000000000000;

impl StuffingStrategy<u64> for NanBoxStrategy {
    type Other = f64;
    fn stuff_other(inner: Self::Other) -> u64 {
        unsafe { std::mem::transmute(inner) } // both are 64 bit POD's
    }
    fn extract(data: u64) -> Unstuffed<usize, f64> {
        if (data & QNAN) != QNAN {
            Unstuffed::Other(f64::from_bits(data))
        } else {
            Unstuffed::Ptr((data & !(SIGN_BIT | QNAN)).try_into().unwrap())
        }
    }
    fn stuff_ptr(addr: usize) -> u64 {
        // add the QNAN and SIGN_BIT
        SIGN_BIT | QNAN | u64::try_from(addr).unwrap()
    }
}

// a very, very crude representation of an object
type Object = HashMap<String, u32>;

// our value type
type Value = StuffedPtr<Object, NanBoxStrategy, u64>;

let float: Value = StuffedPtr::new_other(123.5);
assert_eq!(float.other(), Some(123.5));

let object: Object = HashMap::from([("a".to_owned(), 457)]);
let boxed = Box::new(object);
let ptr: Value = StuffedPtr::new_ptr(Box::into_raw(boxed));

let object = unsafe { &*ptr.ptr().unwrap() };
assert_eq!(object.get("a"), Some(&457));

drop(unsafe { Box::from_raw(ptr.ptr().unwrap()) });

// be careful, `ptr` is a dangling pointer now!

MSRV-Policy

stuffs current MSRV is 1.34.2. This version can get increased in a non-breaking change, but such changes are avoided unless necessary. Features requiring a newer Rust version might get gated behind optional features in the future.

stuff's Issues

Clean up API and code

The API kind of sucks with is_other/get_other vs just a single get_other that returns an option.

Also ownership is kind of messed up and requires mem::forget sometimes (the forbidden function). Use more ManuallyDrop<T>.

And just in general this isn't terrible but also not great

Impl Backend for [u8;N]

Use [MU<u8>;N] as the storage

Rename `extra` to `other`

extra is confusing and implies an intersection instead of union

add `Backend::from_usize`

This method allows you to write strategies that are generic over the backend, which can be useful

Add feature to stuff *extra* data into a pointer directly instead of having a union

This would allow for pointer tagging directly, and could even be made safe maybe!

find a way to tell what this crate is actually about in a coherent way

Better examples

NaN-Boxing is quite simple, but not ideal. It's ok if it's a contrived example.

MSRV

find the MSRV and keep it as low as reasonable