Idea: on movable self-referential structs

language design
1

One of mainstream approaches to self-referential structs problem is introduction of immovable types. I would like to propose a slightly different, but compatible approach. (probably it was already proposed by someone, so I will be grateful for any links on previous related discussions) For additional context read this thread.

We’ll start with introduction of Move trait, which is probably quite similar to C++ move constructor:

trait Move: Sized {
    unsafe fn _move(&mut self, offset: isize);
}

default impl<T: Sized> Move for T {
    unsafe fn _move(&mut self, offset: isize) {
        let src = self as *const Self;
        let dst = src.offset(offset) as *mut Self;
        ptr::copy_nonoverlapping(src, dst, mem::size_of::<Self>());
    }
}

Now (with some compiler magic) we will be able to write the following code:

struct Foo {
    array: [u8; 16],
    item: &'array u8,
}

impl Move for Foo {
    unsafe fn _move(&mut self, offset: isize) {
        // copy everything to `dst`
        // apply `offset` to the reference in `item` field to keep it valid
    }
}

We use 'array lifetime to notify compiler that array field can not be accessed through safe code. Without re-implementing Move trait compiler will forbid use of field named lifetimes. This way struct author takes full responsibility for maintaining validity of all internal references. In case of heap allocated buffer Move trait will contain only copy_nonoverlapping, as there is no need to change reference in the field.

Additional nice point is that Move trait will allow code to reliably zero out memory after move which is especially important for cryptographic applications:

type SecretKey([u8; 64]);

impl Move for SecretKey {
    unsafe fn _move(&mut self, offset: isize) {
        // copy data to `dst`
        // zero out `src` using `ptr::write_volatile`
    }
}

But there is still a problem (mentioned for example by @withoutboats here), our struct can contain other types parameterized over lifetimes, e.g. Iter<'a, u8> and they can go arbitrarily deep. Because it’s a foreign type we cannot maintain it’s internall references in our implementation of Move. Thus we need some interface to allow us to keep validity of references in it. For it we can introduce OffsetRefs trait (name is temporary):

trait OffsetRefs {
    const N: usize;
    
    unsafe fn offset(&mut self, offsets: [isize; Self::N]);
}

N here is equal to a number of internal references which this type keeps internally and in the most of cases will be equal to a number of lifetimes it parameterized over. So if Iter<'a, T> will implement this trait we’ll be able to write:

struct Bar {
    array: [u8; 16],
    iter: Iter<'array, u8>,
}

impl Move for Bar {
    unsafe fn _move(&mut self, offset: isize) {
        // copy data to `dst`
        // call `_move` on fields if necessary
        // after move call `(*dst).iter.offset([offset])`
    }
}

struct Baz<'b> {
    a: &'b [u8],
    array: [u8; 16],
    field: G<'array, 'b>,
}

impl Move for Baz {
    unsafe fn _move(&mut self, offset: isize) {
        // copy data to `dst` with separate
        // call `_move` on fields if necessary
        // after move call `(*dst).field.offset([offset, 0])`
    }
}

impl OffsetRefs for Baz {
    const N = 1;

    unsafe fn offset(&mut self, offsets: [isize; 1]) {
        // shift `self.a` to `offsets[0]`
        // call `self.field.offset([0, offsets[0]])`
    }
}

Hopefully in the most cases it will be possible to auto-derive Move implementation, so most of authors will not have to implement this trait manually.

The big drawback of this proposal is that moves can result in arbitrary code execution, but on the other hand it provides full control to the programmer over how data is moved, which in some cases can be quite useful. But of course manual implementation of Move should be highly discouraged and used only in the absolutely necessary cases. Another drawback is that it will require to implement OffsetRefs trait for types parameterized over lifetimes on non-heap allocated fields, otherwise it will not be possible to use them in self-referential context without introduction of immovable types.

Unresolved questions:

  • Is there any corner or subtle cases which can not be soundly implemented by this approach?
  • To what extent Move and OffsetRefs can be autoderived? Is it possible to rely only on autoderivation and forbid manual implementation altogether?
  • How should look construction of self-referential structs?
2 Likes
2

I don’t like the thought that moving could result in arbitrary code execution.

It seems to me that one of the following ought to be true:

Either:

  • the compiler could generate all of these Move impls itself, or
  • simply shifting internal references is insufficient to ensure soundness, or
  • writing correct impls is impossible

Though I’m not sure yet which one it is.

3

Assuming that some means of moving a self-referential struct is required, is there any reason it couldn’t be done with ad hoc functions and methods and not involve “language-level moves” at all? e.g. any potentially self-referential Foo simply cannot be moved as far as Rust’s compiler is concerned, but there’s a Foo::move function you have to call that internally uses some unsafe code to perform the move and patch up the self-references (maybe this requires supporting references to uninitialized values?). That would prevent this corner case from infecting the rules of ordinary moves, the same way handling volatility with a pair of read_volatile/write_volatile functions avoids the need for a volatile type modifier.

I assume there’s some sort of use case where moving solely via ordinary function calls is simply unacceptable, but it’s not obvious to me what that would be, since I’m not familiar with any use cases for moving a self-referential type in the first place.

4

The main reason, as I see it, is to make self-referential types completely self-contained, i.e. for outside user they will be no different from usual non-self-referential types. (so for example no need for ?Move trait in generic code)

1 Like
5

There are good reasons why it’s desirable to be able to move arbitrary values without running user code, but even leaving that aside, in Rust today you can move arbitrary values by simply memcpy-ing them, and consequently a lot of existing unsafe code does that. Backwards compatibiliyt requires that we keep that code valid. One way to do that would be to add a marker trait for values that can be moved via memcpy and implicitly add that to the bounds of generic code, i.e., we’d still need ?Move.

2 Likes
6

I’m inclined to agree with @Ixrec that language-level movability isn’t crucial for self-ref structs, but rather ad-hoc methods can be provided if it’s truly necessary for that type.

In either case, movability is a bit of a tangential problem for self-ref structs anyway. The real root of their unsoundness is lifetime unification problems for the field lifetimes. Until that is addressed somehow, no approach can be truly sound with resorting to HRTB closure trickery.

7

Could you please demonstrate it with an example or two?

8

Any lifetime that appears within a struct, as of now, is a parameter of that struct (or 'static, but that’s not particularly relevant here). So a self-ref struct definition might look as follows:

struct SelfRef<'a> {
    pub a: i32,
    pub b: &'a i32
}

There is no lifetime you can pass for 'a that truly expresses the real lifetime of the struct, from its creation until its drop. Rust will allow lifetimes here that are too wide, which causes unsoundness.

Rust’s conception of lifetime parameters for structs is that they must live at least as long as the struct itself, but possibly longer. This means rust assumes that any references within the struct are external to the struct and will remain valid regardless of if the struct is moved or dropped.

This can cause serious problems if you have 2 self-ref structs of the same type, since rust can and will unify their lifetime parameters if it is able to do so:

fn unsound<'sr1> (sr1: Box<SelfRef<'sr1>>) {
    let sr2 = SelfRef { a: 5, b: sr1.b };
    mem::drop(sr1);
    println!("oops crash {}", sr2.b);
}

In this example, we see that, whatever lifetime is used for the parameter of the first self-ref struct, we can create another instance of the struct that copies that lifetime param and becomes entangled with it. We can then drop the original and would be left with a dangling ref.

From this, we can conclude that there is no valid lifetime parameter that we could use, in current rust, to express what’s really going on here. Rust would need a completely new notion of a field lifetime that is borrow checked in a special way to avoid this. The current best hypothesis is “generative existential lifetimes” which would prevent this kind of problem, but that’s a highly non-trivial addition to the language.

7 Likes
9

Thank you! But I had in mind more restrictive notion of self-referential structs. As you’ve probably noticed structs in my examples are not generic over field lifetimes. I should’ve written about it explicitly, but I’ve implied that foo: &'bar T is assumed to point only to data stored in the field bar of the same struct and this invariant should be maintained by Move implementations and struct constructors. Thus in your example construction of sr2 will be rejected by compiler as pointer in the field b does not point to the field a. It’s probably not correct to call such “field lifetimes” as “lifetimes”, but I don’t have a better terminology yet.

10

Right. My point is simply that even if this invariant is maintained by move constructors, rust isn’t currently able to understand that invariant and enforce it correctly, without the addition of a very subtle and complex feature that’s likely far more difficult to implement than any of the machinery surrounding movable types.

11

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.