Free list is not the same before/after serialization

[Uriopass]

I'm not sure if this is intended (it probably is). But the freelist is not necessarily the same after a serialization cycle.

This means that doing operations_1 -> ser -> deser -> operations_2 does not result in the same keys as operations_1 -> operations_2

This is a bit troublesome as I wish my program was deterministic even through serialization cycles as it is necessary for lockstep networking.

If this is intended, I can fork and serialize the freelist, or maybe this crate can provide another serde implementation using serde(with = "..")).
If this is not intended, I can try to make an example to reproduce.

[orlp]

It's neither intended nor unintended, I hadn't considered your usecase yet. I might consider serializing the freelist structure as well for slotmap 2.0, but I'll have to have a good think about what that means for serialization size, backwards compatibility and the performance checks needed to verify a freelist is correct after deserialization.

I assume the problem comes up with iteration order? Could you give some more context.

[Uriopass]

The problem comes up with iteration order and key values yes.

For more context, I am implementing a replay system for my game. Therefore I want to make sure that applying actions successively will always end up with the same state even if it was serialized in the middle.

Take a random player: plays game -> saves -> loads the next day -> continue playing

The actions the player can take have slotmap ids associated with them, for example "Built road between this IntersectionID and this IntersectionID"

Now imagine the player wants to watch his replay, he starts from an empty world and replays his action. But since he doesn't save/load during those actions, the state is not the same anymore and the keys in the replay are wrong! That's the issue I'm trying to fix.

[Uriopass]

but I'll have to have a good think about what that means for serialization size, backwards compatibility and the performance checks needed to verify a freelist is correct after deserialization.

Note that you can have multiple serializers for the same object. You can provide a separate module to be used with serde(with)

[orlp]

I'm leaning towards serializing freelist state in slotmap 2.0, but that will be some time away. I'm not particularly tempted to duplicate all of the serialization code (and tests) to provide an alternate serializer.

I'm afraid that for now your best option is forking until I get around to this.

[Uriopass]

Thank you for your quick responses.

[Uriopass]

For your information, I have published the fork on crates.io. You can see the changes I made in this commit if you're interested.

[orlp]

For your information, I have published the fork on crates.io. You can see the changes I made in this commit if you're interested.

I'm afraid this is not sound. Someone could send you a serialized freelist that accesses out-of-bounds memory. You have to check that the freelist is all in-bounds, unique and actually linked.

[Uriopass]

You're right, I didn't think about this kind of protection. I'll fix it and yank the old ones.

[Uriopass]

I implemented deserialization validation if you want to take a look: https://github.com/Uriopass/slotmapd/commit/90ffc61409bfa0b2adb3b65a618b0f071ec29f83

I might have missed an invariant. The HopSlotMap was definitely the hardest to understand. Thankfully quickcheck was a lifesaver.

[Fuuzetsu]

I'd just like to add our 2 cents: we have a very similar problem.

We have some deterministic software that goes forward in time and takes regular snapshots, serialising its state as it goes along. Sometimes we want to go back to a snapshot to have a another look at something. Once we do this, going forward again from the snapshot causes a divergence in state: we get different keys when resuming from snapshot and when just going forward.

I'll have a look at the fork mentioned here but we're looking forward to this working out of the box.