Forem: jmaargh

An alternative Any type?

jmaargh — Mon, 16 Oct 2023 15:28:31 +0000

Rust's Any type is pretty cool. You can use it to do runtime type reflection, or downcasting, or dynamic typing, or other fun things. However, there are a couple of slightly annoying things about it:

TypeId is currently 128 bits. This is because it's some hash of the concrete type, so needs to be long enough to reasonably avoid hash collisions.
Getting TypeId from &dyn Any requires two dereferences: first you follow the vtable pointer to find the pointer to Any::type_id(), then you call that function.

In the vast majority of cases this is totally fine (which is why the excellent libs team implemented it this way). You're unlikely to be bottlenecked on either of these. But neither is ideal: u128 operations can be pretty slow on older or embedded chips and nobody likes more indirections than are necessary.

It occurs to me that both can be circumvented, if you're willing to give up one thing: stability of TypeId values. That is, if you don't need to assume that TypeIds are the same between different binaries. This seems to be a fairly small thing to give up in most cases. How often are people serialising TypeIds? Doing so is already a bad idea as they're not guaranteed to be stable between Rust compiler releases.

The idea is to simply store the type ID directly in the vtable and have the compiler guarantee that, in the context of the current build, the ID is unique. No second indirection, no IDs longer than necessary.

Doing this "properly" would require some compiler hacking. But I did come up with a way it can be hacked around: I call it PointerAny and TypePointer. The trick is to use a pointer to a method of the PointerAny trait as the type ID itself.

Let me explain. First, we define the trait

pub trait PointerAny: 'static {
    fn type_ptr(&self) -> TypePointer;
}

This is exactly like core::any::Any, no surprises here.

We also need a TypePointer instead of TypeId. This will be the address of a function pointer (as discussed above), so let's do that:

#[derive(PartialEq)]
pub struct TypePointer(usize);

For the sake of simplicity I'll just use a usize here. Really you'd want NonZeroUsize or something.

Getting this TypePointer statically is easy, we just take the address of the function pointer that's stored in the vtable:

impl TypePointer {
    fn of<T: PointerAny + ?Sized>() -> Self {
        Self(<T as PointerAny>::type_ptr as _)
    }
}

But this isn't enough to be useful yet. We need a way of getting TypePointer from a &dyn PointerAny. In principle, I feel like there should be a good way of getting the compiler to tell us the address we're looking for. After all, the compiler knows how to call this function, so it therefore knows how to find its address. Unfortunately I don't know how to get the compiler to tell us that address, so instead I'm leaning on some very ugly unsafe code:

impl TypePointer {
    fn from(object: &dyn PointerAny) -> Self {
        let pointer = unsafe {
            let (_data, vtable): (*const (), *const usize) = core::mem::transmute(object);
            // vtable consists of:
            // - drop pointer
            // - size
            // - alignment
            // - method pointers
            // In that order. So this gets us pointing to the first method.
            let method_pointer = vtable.add(3);
            // We want the pointer for this first method
            *method_pointer
        };
        Self(pointer)
    }
}

This requires a little explanation. A wide-pointer like &dyn PointerAny consists of a pointer to the type's data, followed by a pointer to the vtable. That's what the transmute call is unpacking here.

Rust, unfortunately for us, doesn't guarantee any particular layout for vtables. However, from what I can gather the current implementation is as outlined in the comment. First there's a function pointer to the drop implementation, then there are usizes for both the size of the type and its alignment, then there are points to each method. Since we only have one method on PointerAny, that pointer should be an offset of 3-usizes from the base pointer. Which is what we take.

Now you may have noticed that we haven't actually implemented PointerAny yet. That's because we don't ever actually want to call the PointerAny::type_ptr method: we just want the compiler to give it a unique address per-type. Therefore, its implementation is the least important part of this puzzle (but still essential, as we need the compiler to actually generate it and its address). So we can just implement it in the obvious way:

impl<T: 'static + ?Sized> PointerAny for T {
    /// Be careful! If you have a `&dyn PointerAny`, then prefer calling
    /// `TypePointer::from` over this to avoid the extra indirection.
    fn type_ptr(&self) -> TypePointer {
        TypePointer::of::<T>()
    }
}

Note, if you call this function from a &dyn PointerAny then you lose the benefit of avoiding the indirection: prefer calling TypePointer::from or TypePointer::of directly.

It's also interesting that PointerAny::type_ptr is far nicer than TypeId::from, despite doing the same thing, because at this point we already know the concrete type so can just get the function pointer directly.

And that's it! We can now dynamically type-check just as with core::any::Any!

pub fn is_same_type(first: &dyn PointerAny, second: &dyn PointerAny) -> bool {
    TypePointer::from(first) == TypePointer::from(second)
}

pub fn is_type<T: PointerAny>(object: &dyn PointerAny) -> bool {
    TypePointer::from(object) == TypePointer::of::<T>()
}

Full code on playground.

So we've successfully addressed the two "shortcomings" discussed above:

Our new TypePointer is only a usize, which is ideal for almost every architecture.
We only do one pointer dereference in TypePointer::from.
We've also gained TypePointer being non-zero, which allows niche optimisations for Option etc. (if we'd used NonNullUsize)

On top of that we still have:

TypePointer::of is still a compile-time constant (no indirection)
In principle this could all be done in a compile-time const fn-compatible way (though you'd want to be really careful about the const fn use of pointers - perhaps this isn't possible yet).

So what are the tradeoffs? What have we lost?

Stability of TypePointer values: if you recompile your program, even with the same compiler, these may change. Don't ever serialize these TypePointers: they're just pointers after all.
Stability of implementation. I had to write some very ugly unsafe code to get this to work, because I couldn't fine a stable way to get the compiler to tell me the address of a vtable method from a wide pointer. In principle this needn't be so ugly, but I just could not find a way of doing it without assuming the structure of the vtable.
Correctness? The current implementation assumes that the compiler will generate exactly one version of PointerAny::type_ptr for any given type (when needed). That is, there is a one-to-one correspondence between addresses of PointerAny::type_ptr and types themselves. I'm not 100% sure this is a guarantee, but I've assumed it's true. It's known that Rust can generate multiple vtables for the same types - otherwise we could just use the vtable address itself and have zero indirections - but I've assumed that the pointers contained are stable.

It's also interesting that we could have implemented TypePoitner over core::any::Any rather than defining a new Any type. The only assumptions we need are that (a) the trait is implemented for every 'static type, (b) there are unique addresses for at least one method per type, and (c) we know how to find that address from a wide pointer.

I'd love to hear what people think of this. There are probably some things here that are wrong (well, even more wrong than the TypePointer::from implementation), so let me know!

Discuss on reddit

Rust's `Send` and `Sync`, but actually the opposite

jmaargh — Tue, 28 Mar 2023 15:33:46 +0000

This post is my personal notes for grokking Send and Sync in Rust. It's not formal, and will assume that you're basically familiar with concurrency and synchronisation, as well as Rust's main wrapper types. In particular, remember that Rust values are always owned by exactly one variable and taking references must satisfy aliasing xor mutability.

Here's the secret: you shouldn't be worrying about Send and Sync. They're the default. Almost everything is Send and Sync, and the compiler will auto-derive them for every type it can. The issue is !Send and !Sync, or really just: !Send.

So what is `!Send`?

A type is !Send when values can't be owned on one thread and then moved to another. Because of single-ownership it couldn't be owned by two threads simultaneously, this is a restriction across the whole life of the value.

!Send := this value is locked to the thread that created it

That's the core concept behind both !Send and !Sync. I'll get to when this is the case later, but first let's talk references.

If we can have T: !Send, we can also have &U: !Send since T could be &U. This case is particularly interesting, since if we own a value of type T we can create as many &T values as we like.

This means that unless &T: !Send, we can have as many &T values on as many threads as we like. This is great for the most part: &T is immutable so there are no data-races... unless T contains interior mutability. Interior mutability exactly means being able to mutate T behind a &T reference. This sounds like a recipe for data races! In such cases we'll need &T: !Send to prevent them. This is so important that it gets its own name...

Surprise `!Sync`!

T: !Sync simply means &T: !Send. Interpreting a bit, !Sync means that a value cannot be referenced by multiple threads at all.

!Sync := references to this value are locked to its thread

This almost means that !Send implies !Sync. After all, if a value cannot be used by more than one thread at different times, how could it possibly be allowed by more than one thread at the same time? This is often true, but not a logical requirement, because !Sync is about whether shared references (&T) can be used on multiple threads at the same time, not the value itself. It is possible (but fairly rare) for a type to be !Send but still Sync, for example if your type is backed by some thread-local resource but all behaviour visible through &T does not depend on it.

So is this type `!Send` or `!Sync`?

There are a bunch of rules of thumb. But I think the key question they boil down to is: could this type be used to move a !Send value (which may be a &T: !Send) to another thread?

Rules of thumb for !Sync:

Your type transitively contains any !Sync type, unless wrapped by a Mutex or similar synchronisation primitive.
Your type contains interior mutability which is not synchronised. For example, it contains Cell or RefCell.
If you can use a &T to take ownership of any !Send type.
- This is normally the case if your type is !Send itself.
Your type contains raw pointers and you haven't manually proven and implemented Sync.

Rules of thumb for !Send:

Your type transitively contains any !Send type.
Your type is a handle to a resource which it owns non-uniquely, and access to that resource is not synchronised.
- For &T, this is exactly rule 2 for !Sync, since if T has interior mutability that means that &T is a shared-ownership handle to T.
Your type contains raw pointers and you haven't manually proven and implemented Send.

Examples

Rc -- This is a handle to a resource that is jointly owned, therefore !Send since (for example) Rc::get_mut is not synchronised. Moreover, Rc has interior mutability for the reference count, which is unsynchronised, so !Sync.
Arc - Avoids the problems of Rc by synchronising the reference count and access appropriately using atomics, thus both Send and Sync.
RefCell -- Archetypal example of interior mutability with no synchronisation, therefore !Sync, however since the wrapped value is unqiuely owned then RefCell is Send when the wrapped value is.
Mutex -- If it contains a !Send type then it's !Send + !Sync since it provides full ownership of the contained type. Otherwise, it is both Send by unique ownership of a Send, and Sync by enforcing synchronisation itself.

Raw pointers are interesting. Rust marks all raw pointer types as !Send and !Sync, but moving them (and their references) between threads isn't in-and-of-itself a problem. The problem comes when you try to use (that is, dereference) that pointer. That action is already marked as unsafe, so Rust could have allowed them to be Send and Sync, but it is considered so easy to break Send and Sync with raw pointers that you need to additionally implement the corresponding unsafe traits to mark your type as Send or Sync.

No free `Send` wrapping

"I've got this annoying value, how do I just make the damn thing Send and Sync already!?" I hear you cry.

Bad news, I'm afriad.

The better news is that if the type is !Sync but is Send, then you can wrap it in a Mutex or similar synchronisation type and that will make it both Send and Sync.

The very bad news is that !Send types can only be made Send by unsafe impl Send for T -- which you should absolutely not do unless you very much know what you're doing.

Truly !Send types (that is, basically anything !Send except carefully used raw pointers) are stuck on their thread. This is the entire point of the feature, anything else and you're exposed to data races.

Your alternatives for dealing with !Send types is to, for example:

Serialise the data contained and send that to another thread where it can be re-constructed.
Use channels or other inter-thread communication to indirectly "talk to" the !Send thread when needed.

When do I force `!Send` or `!Sync`?

It's possible that you're writing some struct that would make no sense to send to other threads (or send references to other threads), but the compiler cannot work this out itself. This is rare, since the compiler will generally work it out before you, but possible if the issue is one of higher-level correctness that the compiler cannot reason about.

For example, suppose you're wrapping some library behind FFI and you know (from the library docs) that the resource you're working with is thread-local. However, the "handle" that library gives you to said resource is just a bare primitive, like u32. Rust has no idea that u32 is !Send (acting more like a pointer) until you tell it.

Right now, it's not terribly easy to force !Send or !Sync, since negative impls are only available on nightly. The work around is to use a PhantomData of some type that already has the !Send or !Sync you require, so that gets inherited. For example, winit::EventLoop contains a PhantomData<*mut ()> explicitly for this purpose.

When do I force `Send` or `Sync`?

It is, of course, possible to manually implement Send and Sync on something the compiler has decided is !Send and !Sync. This is how std collections (as well as others) which work on raw pointers implement Send and Sync appropriately.

This power -- like any use of unsafe -- should absolutely not be taken lightly. Read the nomicon, reason carefully, and write good tests. Don't just unsafe impl Send because you're frustrated, that way lies Undefined Behaviour and Madness.

Forem: jmaargh

An alternative Any type?

Rust's `Send` and `Sync`, but actually the opposite

So what is !Send?

Surprise !Sync!

So is this type !Send or !Sync?