# Savestates

As I started getting more and more operating systems to boot, it took longer and longer for the emulator to go from power-up to wherever the bug was. They're overkill for something like, say, the BIOS POST, but they were definitely worth the time investment when I was debugging obscure SSE errors late in Windows 7 boot. 

Savestates capture a "snapshot" of the current emulator state, preserving it in a form of suspended animation. They can be "thawed" out and the VM spun up, without having to go through the same boot process again. 

They have the following advantages: 

- You can thaw out a virtual machine an unlimited number of times
- You can "overlay" multiple virtual machines on top of each other using the same base image (this is very useful for very large operating systems, like Windows XP) 
- They speed up boot and save bandwidth, which is crucial on the browser
- They're good for debugging
- All the other x86 emulators have this!

Unlike many other emulators, Halfix allows you to load a savestate mid-execution without restarting the VM. In fact, to check early iterations of the savestate mechanism, the `DISABLE_RESTORE` macro was commented, making the emulator completely save *and* restore its state every 100,000,000 instructions or so. 

## File Format

Savestates use a format called `bjson`, a simplified form of the [UBJSON](https://ubjson.org/) specification that only focuses on saving chunks of binary data. This works well for smaller data sets, where the additional cost of opening, reading, and closing files would be more than a simple `memcpy`. 

For larger sets, like RAM, data is stored in a separate file and is *not* encoded inside the savestate itself. 

Savestates begin with a header, `0xC8C70FF0`, [an infamous number](https://en.wikipedia.org/wiki/Pentium_F00F_bug). It's followed by the version, which is set to `0` at the moment. The file itself is structured like this: 

```c
struct bjson_file {
    uint32_t header;
    uint32_t version;
    struct bjson_object root_object;
};
```

At the moment, there is no way for the top-level object to be anything other than an object because there is no need for it. A BJSON object looks like this: 

```c
struct bjson_object {
    uint8_t type; // Set to 1
    uint8_t length; // Number of key-value pairs
    struct bjson_key_value {
        zero_terminated_string_t key;
        union {
            struct bjson_object value_obj; // value_obj.type == 1
            struct bjson_data {
                uint8_t type; // == 0
                uint32_t length;
                uint8_t data[length];
            } value_data;
        };
    } entries[length];
};
```

It seems complicated, but it's actually not. Each object has a `type` header (which should be set equal to one, for reasons that will become clearer later on) and `length` field, which denotes the number of key-value pairs. Right now, there can be a maximum of 255, which is more than enough. 

The key-value pairs start immediately after, and they continue until they've been completely parsed. Because key-value pairs are inherently variable length, the only way to determine the true size of this `bjson_object` is to iterate through each key-value pair, determining the size. 

A zero-terminated ASCII string serves as the key. All characters are valid, except for `\0`. Then it's followed by a single-byte field called `type`. If `type == 1`, then the entry is an object, and that type byte actually doubles as the first byte of the nested `bjson_object`. If `type == 0`, it's followed by a 32-bit length containing the byte length of the data and a series of bytes. 

This format is so simple, in fact, that the entire parsing requires less than 40 lines of code. 

## Structure

The file looks like this: 

```json
{
    "cpu": {
        "field1": [0, 0, 0, 0],
        "field2": [0, 0, 0, 0]
    }, 
    "pic": {
        "field1": [0],
        "field2": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    }
}
```

The actual structure of the file is determined by the various `*_state` functions in each hardware component or CPU module. The code to save/restore these modules was automatically generated by `tools/autogen_savestate.js` from the C header files. There's a little bit of fudging to get the struct names right, and it's not exactly the neatest code, but it gets the job done. 

`*_state` functions are intended for both serialization and deserialization. The generated code passes pointers to various emulator fields, which are either copied into the output stream or overwritten with the values from the parsed BJSON file. 

In some components, like the CPU or VGA, some additional work is required to load auxiliary files and refresh various structures. For instance, savestates don't preserve the values or states of the TLBs because they're transient, temporary structures; consequently, they must be updated using the data that was either saved or restored. 

## Drives

Some emulators like Bochs require to duplicate your hard drive image as part of your savestates. Others simply include the modified sectors as part of the file. The latter method is clearly the superior way, since the amount of data written to a drive is minimal compared to the amount of data read. 

Still, some operating systems write hundreds of megabytes to disk on boot, and a savestate that size would have been a showstopper for anybody that wished to use them on the Web. Thus, savestates write out modified sectors to a directory inside the savestate, which are loaded on demand. 

Hard disk images are intrinsically linked to a hard drive emulator (otherwise, why would they be there?), so the story starts in `ide.c`. Based on which drives currently have media in them or not, the IDE emulator chooses to explore the following key-value pairs in greater detail: 

 - `ide0-0`: Primary master
 - `ide0-1`: Primary slave
 - `ide1-0`: Secondary master
 - `ide1-1`: Secondary slave

The story continues in `drive_internal_state`, which preserves the following bits about the device: 
 - The size
 - The number of paths
 - The number of blocks

An important note about chunked disks is that each file is named `blk%08x.bin.gz`, where `%08x` is the block ID. In the original directory, where the full disk image is, blocks will be contiguous, numbering from 0 to the total number of blocks. In a savestate, however, this is not always the case. 

Blocks are differentiated by their paths: savestates will have a different path than their parents, and that's what enables the emulator to decide between a block present in the original image and one in the newer image. During execution, the emulator will pull some blocks from `original_disk/` and another from `savestate/ide0-0/`. 

You can also overlay multiple savestates, forking them as needed. There can be a total of 255 different paths; you can have block 1 pulled from Savestate 7 and block 2 from Savestate 2 and block 3 from the original image. The total number of directories that images can be pulled from is the `path_count` field. For example, a savestate might look like this: 

```
Path prefixes (path index vs. path): 
 0: win95/
 1: savestate1/ide0-0/
 2: savestate2/ide0-0/

Path index array (block vs. path index): 
 0: 0 (win95/)
 1: 1 (savestate1/ide0-0/)
 2: 2 (savestate2/ide0-0/)
 3: 2 (savestate2/ide0-0/)
 4: 1 (savestate1/ide0-0/)
 5: 0 (win95/)
 6: 0 (win95/)
 ... 
```

If block 3 is requested, for instance then the file `savestate2/ide0-0/blk00000003.bin` will be read, as opposed to `savestate1/ide0-0/blk00000003.bin` or `win95/blk00000003.bin`. 

If the savestate is being read (and emulator state is being restored), the following happens: 
 1. The path prefixes are read and stored in an array
 2. All currently existing blocks are freed
 3. Each block's `pathindex` is updated

If the savesate is being written (and emulator state is being saved), the following happens:
 1. A new directory is created, representing the name of the drive
 2. The name of this newly created directory is added to the path prefix array.
 3. Each modified block is written to this new directory

This leads to some more short-term complexity, but it allows for dynamic, lazy loading of drive data. 

## Limitations

Device configuration must be *exact*, but no checking is done. For instance, if your savesate has 32 MB of RAM, configure the emulator with 32 MB beforehand. The savestate mechanism won't automatically size down the memory for you, and you're going to run into problems if you increase or decrease the amount of memory without letting the computer know. 

There are probably many chances for buffer overflow bugs. Hopefully nobody feeds bad data into the emulator. 

Currently, all integer fields need to be in the same endianness as the machine that the savestate was created on. This isn't a problem in many cases because Halfix likely only supports little-endian machines. 
