Soundness review: Long-lived "reborrows"

When attempting to use the two-phase commit solution I posted last week, I discovered that it couldn't handle dependency chains so I had to come up with a completely new design:

I unfortunately couldn't come up with a non-unsafe design that did everything I wanted it to:

  • Revertable actions should statically lock the object they operate on via &mut until they are either committed or reverted.
  • Revertable actions should be able to return a reference into the object they modify (the exclusive lock will continue as long as this result exists)
  • The result of a revertable action should be usable before commit/revert by a second action, and the combination should commit/revert as a unit. (The ability to revert the secondary action and then do something else with the primary would be nice but isn't required.)
  • Dropping/forgetting a revertable action should be safe and equivalent to a commit.
  • Reverting a chain of operations should be linear-time wrt. the length of the chain. I think this requires caching the intermediate references.

This is undoubtedly the most complicated piece of unsafe code I've attempted, so I'd appreciate any thoughts you may have on it. I'm only really concerned with asymptotic efficiency here-- If there's a safe abstraction with only a constant-time penalty, I'll happily use it. In addition to any general soundness issues, there are a couple of things that could stand some extra scrutiny:

  • The implementor's contract for RevertableOperation: Is it unsound or unclear?
  • Does chain() accidentally release one of its static locks due to incorrect lifetime annotations?

I don't see any obvious ways to break it. As for chain, I'd feel a lot better about it if it didn't have two lifetimes:

impl<'a, T: 'a, Op: RevertableOperation<'a, Out = &'a mut T>, Cleanup>
    RevertHandle<'a, Op, Cleanup>
    Cleanup: FnOnce(),
    pub fn chain<Op2: RevertableOperation<'a, In = T>>(
        op2: Op2,
    ) -> Result<RevertHandle<'a, Op2, impl FnOnce()>, Op2::Err> {
        let (result, rev_args) = self.into_raw_parts();

        RevertHandle::new_with_cleanup(result, op2, || unsafe { Self::revert_raw(rev_args) })

That makes a lot of sense. Of the top of my head, I can't think of any scenarios where that would cause a problem: I just wrote the first thing that seemed plausible.

Well for one I think you were missing the contained-in bound for the two lifetimes, but ignoring that, your RevertableOperation struct is currently invariant wrt. the lifetime, but having two lifetimes would let you shorten the lifetime. So in that case you would have verify that it is sound for RevertableOperation to be covariant if you want two lifetimes.

1 Like

I'm using this to implement atomic updates of container structures with 'static data points. Each subcontainer is allowed to reject the entire operation, and some of them split the points into pieces to be stored separately.

Lifetime-shortening doesn't seem particularly important to making that work, so I think I'll spend my complexity budget elsewhere.

Thanks for the review. Would adding a method like this to RevertHandle<'a,Out=T> be safe (i.e. not let any 'a references escape, even if some are embedded in T):

fn preview<F,Out>(&self, closure:F)->Out
where F: 'static + Fn(&T)->Out,
      Out: 'static
{ /* ... */ }

My logic is that the static bound on F ensures that it doesn’t contain anything like Rc<Cell<&'a>> (and similar for Out)

Why do you need 'static on F, but not &T? Fn already takes care of limiting the acceptable functions to callable-multiple-times (although I rarely see Fn without Send + Sync, because Fn does not prevent mutation through UnsafeCell & co. and is thus not thread-safe by itself, i.e. FnMut should be fine, too). 'static on Out already does the job of limiting the return values. :thinking:

T is the future return value of RevertHandle::commit(), which may need to be a reference into the original object being manipulated (to support downstream operations). Until then, though, the 'a lifetime on references internal to T is a lie: revert will invalidate them by creating an &mut from the pointer they’re derived from (if you can think of a safe alternative, I’d be happy to use it instead)

If T:'static, I’m going to directly implement Borrow{,Mut}<T>: they’re obviously safe at that point.

My question here is how (if?) I can expose a non-unsafe function that allows some limited view into the produced value, to decide whether it should be reverted.

To avoid the conversation getting too abstract, the particular situation I’m looking at is this:

I am trying to build a indexing container that holds redundant copies of the same data, but with different memory layouts. To insert a new record, I want to insert it into the primary store first, and get back a reference to the inserted record (as it may have been modified by, e.g. an auto-primary-key generator). The index store(s) then need to look at that record to do their own insert operations.

If any of the indices can’t insert due to a constraint violation, though, I need to be able to rollback any of the operations that are already complete.

I hadn’t put much thought into Fn vs FnMut vs FnOnce. They should all be the same from a safety perspective, and the function will only be called once, but I also want to discourage using this to produce long-lasting effects from an operation that still might be rolled back.

Actually, changing to Fn* was a last-minute change to make the question simpler, but it caused problems with the question :frowning: . In reality, that would be a custom trait with a method that accepts some kind of generic parameter.

Is your project a standalone database or just an ad-hoc database for another project? If it's the latter, I'd normally recommend using an existing database, that comes with ACID support. What's your motivation behind doing it yourself? Is it a matter of learning, performance, security, fun, etc.?

This is for my MS final project, which is to build a relational algebra engine on top of the std collections (and probably im) that does its query planning statically at compile time.

The goal is to have a common query interface that lets you do memory-layout based performance tuning without major refactoring work in the application logic. For example, adding an index to your storage type should make the relevant queries use it automatically.

1 Like

Is the data persisted somewhere or do operations persist data somewhere? The problem with arbitrary functions is, that they might contain network or file system operations, that cannot ever be guaranteed to be undoable.

Each operation is a struct (which contains all of its arguments) that implements a pair of functions via an unsafe trait:

  • forward(self, &'a mut In)->Result<(T, Log), Err>
  • reverse(&mut In, Log)

In, Log, and Err statically cannot refer to 'a, but T can. The implementor’s contract for that trait says that, to be sound, forward must ensure that dropping/forgetting the returned T will prevent any future uses of the &'a mut In. This is necessary so that the RevertHandle can use the same pointer to create the &mut necessary for giving to reverse.

From the caller’s perspective, the RevertHandle holds a mutable reference (and therefore exclusive lock) to the object being modified until either commit() or revert() is called. And, if the T returned by commit uses the 'a lifetime it will also keep the same exclusivity.

So, as long as I can prevent the 'a lifetime annotation from escaping the preview function, it should be sound (but not necessarily correct) for all closures. I think it’s also guaranteed to be correct if T doesn’t expose any interior mutability APIs (There’s no way to enforce this inside the type system; perhaps it should be added to the unsafe contract text)— Changes outside the object protected by the RevertableOperation are not recommended, but are somewhat out of the purview of this mechanism.

As for chain(), it takes an operation value which means the implementor has promised to behave by implementing an unsafe trait. Its reverse is supposed to be infallible, and if the &'mut In provided isn’t equivalent (in some poorly-defined way) to the way it was left at the end of forward, there’s a bug somewhere and panicing seems like a reasonable course.

It’s also relevant to note that my current planning is around the APIs necessary for people implementing new storage backends and access adapters: They aren’t necessarily the way end users are expected to interact with the system, but will probably be exposed (because extensions need them).

1 Like