What about: "container_of"-style pointer arithmetic?

[RalfJung]

On unstable Rust, we can finally have a sound unrestricted offset_of! macro (as already implemented in the memoffset crate). But one interesting open question remains: what about a macro like what @Amanieu called container_of! in Gilnaa/memoffset#21? That macro compute a pointer to the "outer object" given a pointer to some field.

The problem with that macro is that it is very hard to use with aliasing rules as strict as Stacked Borrows, but I also see no good way to adjust Stacked Borrows to support this without losing many optimizations. Basically, the restriction is that only raw pointers may be used when computing the field pointer from the "outer object pointer". Any intermediate reference asserts that this and all derived pointers may only be used for the memory range covered by this reference, making container_of! incorrect.

I don't see a fundamental reason why a Rust aliasing model has to constrain pointers like that. However, I do think it is crucial that we may not just use a reference to one field for a sibling field if a reference to the sibling field exists. That would be illegal aliasing with that sibling reference. So we might be able to relax Stacked Borrows a bit, but not a lot.

I am not sure if a container_of! macro is still useful with all these restrictions, it certainly is non-trivial to use.

[Lokathor]

This is used in allocators, among other things, so it needs to be supported.

[comex]

However, I do think it is crucial that we may not just use a reference to one field for a sibling field if a reference to the sibling field exists. That would be illegal aliasing with that sibling reference.

Even if both references are immutable, or only if one is mutable?

For what it's worth, I think it would be nice if the compiler could do scalar-replacement-of-aggregates (i.e. splitting a structure-typed variable into individual variables for each of the fields, which can then potentially be stored in registers rather than memory) even when a reference to one of the fields escapes. This would break container_of, since the fields would no longer be stored adjacently in memory. However, we seem to be getting along well enough without that optimization, and I agree with @Lokathor that it's essential to support container_of at least in some form.

In theory there could be a per-struct switch for whether to allow that kind of optimization or allow container_of. Not sure which should be the default.

[Lokathor]

I think the natural answer is that repr(Rust) assures nothing (allowing the optimization) and repr(C) makes it more like C (blocking the optimization).

I'll note that this very day I saw at least one "libc shim" that offers malloc/realloc/free and is totally broken when the ability to do a "container_of" maneuver isn't allowed.

[RalfJung]

Even if both references are immutable, or only if one is mutable?

Certainly yes to the second. A mutable reference is a unique pointer, it must not alias with any other reference.

This is used in allocators, among other things, so it needs to be supported.

Can and do allocators ensure that only raw pointers are used when computing the "field pointer" (the argument to container_of!) from the "base pointer"?

[RalfJung]

For what it's worth, I think it would be nice if the compiler could do scalar-replacement-of-aggregates (i.e. splitting a structure-typed variable into individual variables for each of the fields, which can then potentially be stored in registers rather than memory) even when a reference to one of the fields escapes.

Hm, that is a separate concern. Note that repr(Rust) doesn't save us here; repr(Rust) means the layout is unspecified but offset_of! should still work. I am not sure how to specify a language in a reasonably simple way that allows this.
(I think C may allow this optimization, making container_of-style code illegal in C. But of course tons of code still does it in practice and we all just hope things don't fall apart. I do not consider that an acceptable outcome for Rust.)

[Lokathor]

Can and do allocators ensure that only raw pointers are used when computing the "field pointer" (the argument to container_of!) from the "base pointer"?

No.

drop(Box::from_raw(Box::leak(b)));

Here the box becomes a &mut briefly before becoming a box again. This is supposed to be sound according to all the conventions of the standard library.

[RalfJung]

According to all aliasing models proposed so far, it is not sound for the allocator to use container_of! then.

Seems like this will be interesting.^^

[comex]

Hm, that is a separate concern.

Well, have you thought about which other optimizations may be impacted by this?

[RalfJung]

@comex let's open a new issue for this, it's really off-topic here. I opened #244.

[retep998]

According to all aliasing models proposed so far, it is not sound for the allocator to use container_of! then.

Seems like this will be interesting.^^

The allocator on Windows already does something similar: https://github.com/rust-lang/rust/blob/7f5a42b073dc2bee2aa625052eb066ee07072048/library/std/src/sys/windows/alloc.rs#L8-L10

So uh, sure would be great to have a solution!