Use fork() on *nix systems for doing save game

[youROCK]

On *nix systems there exists a really convenient system call: fork(). I suppose that you know what it does, but in case you don't here is a brief explanation:

1) It stops the process with all threads
2) Makes a clone of a calling thread by copying the page list of a parent process and marking all pages as "copy-on-write" in MMU and internally
3) Returns twice: in a parent process and in a child one. Parent receives pid of a child and child receives zero.
4) In child process you effectively receive a snapshot of all process memory, you can perform a save in background and then exit

As copy-on-write in fork() just marks the pages as copy-on-write instead of copying their contents, it is much faster than copying all the pages.
Fork takes a couple of seconds if your RSS is very large but it should not be the case for factorio. You can allocate memory for "shared" and immutable resources like sprites by using mmap with SHARED option so these pages are not copied at all. If you do not use huge pages, then the time spent on fork() is roughly 40 ms per GB of resident set size.

I hope that one day windows will get fork() support as well, not only for ubuntu compatibility.

[bobucles]

I assume the purpose here is to allow the game to continue running while the fork processes the save file?

[SyncViews]

Yes, the idea would be that the main process continues once the fork() is done, and the new process could do the save logic. Which could be fairly simple if they never have multiple threads (threads+fork often results in pain).

It seems unlikely that Windows will get a good fork, the process model is very different, and a lot of people use Windows.

That said personally my expectation is that most of the time is used by compression and disk IO, and in my experience dealing with such code, that writing the data out to an in-memory buffer, then throwing that over to a thread to compress and save moved nearly all the work.

[orzelek]

Yes, the idea would be that the main process continues once the fork() is done, and the new process could do the save logic. Which could be fairly simple if they never have multiple threads (threads+fork often results in pain).

It seems unlikely that Windows will get a good fork, the process model is very different, and a lot of people use Windows.

That said personally my expectation is that most of the time is used by compression and disk IO, and in my experience dealing with such code, that writing the data out to an in-memory buffer, then throwing that over to a thread to compress and save moved nearly all the work.

You are skipping most important part. Game needs to prepare save state by accessing current game state. It can't do that from different thread in any way since state could change during saving. Making copy of state is also a tricky one since in memory game state can be 100's of MB.
I believe it could be an option to add for players so if you have lots of RAM you can use this way.

[SyncViews]

That is what the "writing the data out to an in-memory buffer" is. Ideally that would just mean a single iteration over the game state appending to a byte buffer, its then that buffer(s) that get handed over to another thread.

And unless those dat files inside the zip have some extra compression I missed, its only 10's of MBs generally. RAM can do multiple gigabytes per second.

[youROCK]

I suppose that games are usualy having "ticks" and the state is fully sync between ticks so it is a good place to perform fork() without any issues. Also the game already has "save" so it should be already happening. Usage of fork() could provide drastically reduced wait times and the effect would be much more noticable in case of big factories

[youROCK]

It would also help linux dedicated servers as well, and there usually is a plenty of memory available on servers. By the way, fork() is often used by server software (e.g. Redis) when a consistent snapshot of data is required.

[SyncViews]

I suppose that games are usualy having "ticks" and the state is fully sync between ticks so it is a good place to perform fork() without any issues. Also the game already has "save" so it should be already happening. Usage of fork() could provide drastically reduced wait times and the effect would be much more noticable in case of big factories

im sure the developers know as far as this specific game goes, but being 100% sure with fork with threads is a pain in general.

E.g. you might have a thread just streaming background music, you might also have a global heap, the operations for allocating and freeing memory might not be atomic, instead using a mutex. Now when you fork to do some stuff on your safe data, you might want to use that global heap (or maybe some library function you call does), but that music thread was in the middle of something and now you hit a locked heap.

A lot of program built around the fork model just never multi-thread (at least in the parent process). e.g. in a simple model the parent process just sits on a socket accept call, then immediately forks the accepted connection to process.

[youROCK]

The problem you described is actually solved using pthread_atfork and glibc actually defines a couple of handlers, one for dynamic symbols resolution and one for malloc.
Also I should note that music actually pauses when factorio is performing game save so it should not be an issue as well.

[fandingo]

It's not as simple as just forking and it solving all problems. Now you need an IPC mechanism to communicate between the two processes, so the save process can report what happened. That could be implemented simply with waitpid() in the parent, but then you need a separate thread for waiting otherwise the game process is blocked or poll with option WNOHANG. Then you have to handle SIGCHLD and interruption/resumption signals during waitpid() The point is that it's a synchronization of status is necessary, and like all parallel programming it tends to get complex quickly.

Process creation is also highly platform specific. For this solution to be practical, you have to depend on the system administrator enabling memory over commit, even if we're only looking at the Linux platform; otherwise, there is a serious risk of ENOMEM on fork totally breaking the save game functionality. It's fine to recommend or require that on server software because it's technical people administering it and expectations from developers and administrators are different. However, it's a bit much for a video game.

Another thing is data size and volatility. COW sounds really nice in principle and is in most cases. However, it's possible to get into a state where a lot of pages are getting small writes that requires copies from the kernel's memory manager.

I guess the point is that engineering decisions require balancing concerns, and I don't think it makes sense to introduce both platform specific code and depend on specific platform configurations on a piece of software like a video game or probably most other desktop applications. From a technical aspect, it's a really cool solution, and it's fun to dig into the nuts and bolts, but I don't think it overcomes the various costs and risks for this type of project.

[Rseding91]

If you've got a sufficiently fast system the vast majority of the time is spent on copying memory out to be saved and not on disk write or compression.

On my system the save time breaks down like this:

• 85% copying memory
• 10% compressing the save data
• 5% writing to disk

That's assuming you've got a solid state drive.

Factorio already writes out to a memory buffer before it gets compressed. Disabling the "write to disk" portion entirely took my 400 hour save file from 19 seconds to save to 17 which means it's not worth the time to look into any kind of forking for saving.

[prg]

I guess the idea here is that the "copying memory" step would also happen in the child process so you could continue with the simulation immediately in the parent process as the kernel would implement copy on write for you.

[bobucles]

I'm under the impression that the fork() step is being used AS the copying process.

[prg]

fork() itself doesn't yet copy memory contents around, that only happens when it's needed ("copy on write")

[bobucles]

The basic theory seeming to be that an initial state remains preserved while the simulation is free to chug forward, as any changes are immediately forked and allowed to process. Sounds neat in theory, and any system with spare CPU/RAM should take it no problem. Being a nix only thing is kinda iffy though. My only question is how to eliminate the old data without screwing the pooch.

[ske]

vast majority of the time is spent on copying memory out to be saved

This sounds like a half truth. Simply copying memory is fast. Much faster than compressing it.

Did you really mean serializing the game state?

This would make more sense because at serialization many memory locations get touched and a lot of data is collected from all the places. During collection it is transformed and reordered which takes oh so many CPU cycles.

In order to speed this up a lot one would have to change the data structures into something like this:
a) the normal heap for all the background data used to display the game state
b) one huge block of memory where only the current game state is stored. This block _Is_ the content of the savegame file. You can simply memcpy it to another location and compress it there.

You would not want to do it this way because you need two or three interacting structures for every single one object you have now.

[SyncViews]

• 85% copying memory
• 10% compressing the save data
• 5% writing to disk

Something is wrong there, on an AWS T2 micro instance I get over 5GB/s on memcpy. There must be a lot of stuff going on around it, or operations not playing well with the cache and memory subsystem for Factorio to spend so much time "copying memory".

[Rseding91]

• 85% copying memory
• 10% compressing the save data
• 5% writing to disk

Something is wrong there, on an AWS T2 micro instance I get over 5GB/s on memcpy. There must be a lot of stuff going on around it, or operations not playing well with the cache and memory subsystem for Factorio to spend so much time "copying memory".

5 GB/s copying raw concurrent memory around sure. But that's not how actual programs are laid out in memory and we don't want to write out the entire contents of the processes memory to disk.

[youROCK]

I would like to underline the fact that fork() does not copy memory, it only copies page mapping so you can fork() really fast and get a consistent memory snapshot in the child process. You can then traverse memory in basically any order and get copy-on-write behaviour in parent process where only modified pages are copied. Provided that not all pages are updated every game cycle (which does seems plausible because otherwise you would not be able to reach 60 game ticks/sec if you spend 15 seconds traversing all game state), you would get a significant reduction in pause time. If the computer has spare CPU and memory resources then it could continue saving in the background and keep the game going forward.

You can always use "stop-the-world" save mechanism if fork() fails with ENOMEM (or any other error) so there is no real need to ask for overcommit to be always enabled. It could help if you the game really consumes nearly all available memory on the server which does not seem to be reasonable for modern computers.

[kreatious]

I did some digging on how to actually implement this idea on Windows & Linux.

The basic idea is to create and use a memory mapped file region to contain the current game's state. When it comes time to make a save, change the memory mapping to copy-on-write and then create another view of the same memory mapped file, and then spawn another thread do a save in the background. The operating system's MMU will take care of making sure you're saving a consistent view of the game state.

With this method, you won't have to deal with inter process communication. Plus if most of the game state is immutable, that'll bring significant savings on the 85%. And the remaining 15% is just pushed to a background thread where it won't interrupt the user.

On Mac/Linux:
Use mmap() to create a private copy-on-write file mapping (MAP_PRIVATE)

On Windows:
Use MapViewOfFile() to create the memory mapping, and VirtualProtect() to change the memory protection constraint to PAGE_WRITECOPY.