kyren/piccolo

Question: Serialization of entire Lua state

Opened this issue · 2 comments

Not proposing this as a feature but just wondering if it would be possible in theory to save and reload the entire Lua state? Given the "stackless vm" design and the "reified stack", it seems like it may be more possible than in other designs so I thought I would ask. I expect that if nothing else, the Rust callbacks that are stored in the state would be unserializable, but curious what other deal breakers there might be?

kyren commented

Good question! You're not the first person to ask it, and I've thought about this before!

So... there's not really any deal breakers, but there are things that range from somewhat difficult to impossible to do, and it will never be possible in EVERY case to serialize everything. Let me outline what I've thought about so far...

When talking about serializing "state", I'm basically focusing on serializing arbitrary Values, because that covers most of what people mean. That would cover serializing almost everything.. you'd be able to serialize the globals table, any running threads, more or less everything, but it doesn't include things like the registry. No solution we could come up with would cover everything a user would want without a lot of cooperation, so I'm not that concerned about serializing literally everything.

The first, obvious problem is that a network of Values is deeply shared and cyclic. This is fine though, one could imagine serializing any pointer-like Values into a big table and using indirection, avoiding repeated serialization of values with the same pointer. This is workable and there are lots of existing examples of things like this elsewhere (like Java serialization I think?). I'm assuming you already were thinking about this and knew the answer, I just wanted to include it for completeness.

There's also the complexity of threads, closures, upvalues, function prototypes... but I think these are all basically tractable, they're "just" complex, cyclic data structures that can be serialized with value tables and indirection.

The biggest problem is probably dyn trait objects, which is probably why you mentioned callbacks first.

So you mentioned callbacks and that's a good one, those are obviously not serializable as is. Userdata is also not (directly) serializable, as well as Sequence impls, both for the same reasons. Wherever we have a dyn trait object, obviously this presents a serialization problem. The three main objects of this type held by Value are AnyCallback, AnySequence, and AnyValue (the actual value held by AnyUserData), and I'm going to go through these one by one.

AnyCallback

AnyCallback is strangely maybe the easiest case, because they're generally mostly statically defined (the set of callbacks is fixed and known and set at "startup") and not mutable, or the callback API that a user creates can be generally made to be statically defined and not mutable. You have to be careful with this though because even in the current stdlib there are two examples (pairs and ipairs) where there are dynamic callbacks defined, but let's pretend that these can be replaced with plain Lua and static callbacks.

Supposing that every callback is always statically defined and none of them are mutable, a way to serialize all callbacks is to keep a dictionary of known callbacks and serialize some other marker in their place. It would be potentially a lot of boilerplate, but one could imagine keeping every callback function (any exposed stdlib functions and all user made functions) in a lookup table that maps to a marker, and whenever we encounter an AnyCallback, look up the corresponding marker (AnyCallback has Eq, PartialEq, and Hash based on pointer identity). Annoying but doable!

AnyValue

AnyValue is possibly just as easy as AnyCallback but requires a few extra steps. We don't assume that AnyValue is immutable because that's very unlikely. Instead, imagine if we had something like typetag, which allows serializing dyn trait objects directly. I'm not suggesting actually using typetag, because it would require integrating typetag into the AnyValue and this is not necessary (and I think it's impossible / infeasible anyway). Instead, the solution is to make a "registry" of known AnyValue types, and then when encountering an AnyValue, as long as the type is one of the registered types (you can look it up by AnyValue::type_id), you can use that to downcast the AnyValue and serialize it. This is.. basically what typetag is doing, except it works with the strange non-'static downcasting that AnyValue provides. Not so bad!

AnySequence

The juggernaut of the three... AnySequence might actually not be feasible without some annoying changes. The only place AnySequence shows up is inside of Thread, which makes sense because it is the "reified stacks" part of piccolo.

IF we added downcasting to AnySequence then that is a way to serialize it in the same way as AnyValue... it's not a terrible change but it's not great. UserData::new is not a fun method to have to call, you need to provide a projection type via the gc_arena::Rootable macro or a custom type, and you'd have to do the same thing now with AnySequence::new.

Whatever the user's serialization system is, they'd probably have to re-implement the parts of the stdlib that use Sequence impls.. inext shows up again, but then the major one is coroutine.resume, which frustrating because the Sequence impl for coroutine.resume is a ZST!

AnySequence is the one thing I have no clean solution for yet. If I accepted that piccolo was going to support serialization as a first class feature, I think I could make it work by doing what I said and adding downcasting to AnySequence, but the only way it makes that much sense to add is if serialization is part of piccolo. I could register internal serializable types to make the whole thing work, but if I was going to do that... maybe I would just add serialization interfaces to every trait directly? Suddenly this becomes a very invasive change!

Another possible solution for AnySequence is just to.... let it be un-serializable. Reduce the callback API so that no AnySequence will be created, or assume that AnySequence finishes in a bounded amount of time and call Thread::step with the interrupt flag set (it will always make a minimal amount of progress) until the AnySequence is no longer present. The only place AnySequence is actually absolutely required is for coroutines, AND I think any coroutine code that calls coroutine.resume can be turned into a coroutine.yield with a "scheduler" on the outside that actually runs threads (I have a hair brained idea to turn piccolo into quasi continuation passing style (continuation RETURN style?) that is sort of related to this, too).

Anyway, in summary I think it's actually.. surprisingly feasible, but there are several different "levels" of serialization support and each level brings with it new challenges. The trick is figuring out how to experiment with it I think without explicit piccolo support, I actually think that might even be a good "inside out" test to see just how much you can use piccolo in a non-standard way. Maybe it just requires making a lot more of the details of Thread public? I really don't LIKE how Thread works currently which is a big reason it's not more public, but maybe there are solutions that solve both of these things at the same time (like my hair brained quasi-CPS idea).

Edit: Oh also I should mention, there ARE indeed many different levels of serialization support below this too, such as not serializing Threads or arbitrary Values at all! Currently I'm sitting at the lowest level with simplistic serde support, I have piccolo serde integration and some other goodies I super duper mega promise to release in a piccolo_util crate very soon (like... today).

Just reading old issues, and I wanted to clarify some changes that have occurred since I wrote the last response for anyone reading.

First, there have been a bunch of renames, so the objects prefixed with Any have been renamed... AnyCallback -> Callback, AnySequence -> Sequence, AnyValue -> Any.

Second, the "quasi-CPS idea" has been implemented, so the whole thing with coroutine.resume is not a problem anymore. The "scheduler" I mentioned is called Executor, and changing how piccolo worked to use it fixed three or four major problems all at once. The implementation of callbacks like coroutine.resume is now mostly trivial, the real work is done by Executor which keeps an internal "thread stack", and would be trivially serializable if Thread was serializable. There are still quite a few stdlib methods that use Sequences internally, and probably more on the way, but they're probably not as much of a problem as core methods like coroutine.resume that run very long lived Lua code. The remaining core method that I think is the biggest roadblock is pcall, which almost always runs very long lived Lua code, and is only implementable by implementing Sequence (coroutine.resume actually also uses the same sequence impl since it has the same error catching behavior of pcall, but I'm counting them together).

Another change that has been made is that we can now finally implement Sequence with async blocks, which is great because it solves the (imo) only remaining truly terrible part of using piccolo, but it is also a little bad because it would be completely impossible to serialize those sequences.

I think the only sensible way forward would be to make sequences potentially downcast-able, but not require it on everything because it makes the API obnoxious to use, and then only support downcasting for whatever the few subset of "serializable" Sequence impls we would care about (maybe just pcall lol, which is ofc a ZST with no state anyway 😆).

I still think about this issue, it's just ofc lower priority than "completing" piccolo (making it fully implement a respectable version of Lua, getting rid of the really bad pain points, finishing the stdlib, making it "fast enough", etc).