Fxfs on-disk versioning

All “top level” data structures in Fxfs are prefixed with a version number when stored on disk. This includes the superblock, journal, and layer files as well as metadata about the allocator and object stores.

This directory contains the code to deserialize both current and older versions of structures and upgrade older structures to the latest version.

Our versioning is based on a single Fxfs-wide version number stored in LATEST_VERSION consisting of a 24-bit major and 8-bit minor version.

How to perform changes which don't affect storage formats or related structures (i.e. minor version changes)

(These are assumed to be non-breaking changes, if not, then please see below.)

Occasionally we might have need to change an algorithm, for example, the way that a bloom filter or index structure works. In such cases where the format of structures do not change but we wish to identify a filesystem as being written with a specific feature in place, we can bump the minor component of LATEST_VERSION.

How to perform storage format changes / on-disk structural changes (i.e. major version changes)

These changes are always considered to be major version changes. There is some housekeeping that developers need to do, which varies depending on whether the change is considered to be a non-breaking change or a breaking change.

Non-breaking changes

Non-breaking changes are changes where it is possible to migrate the filesystem from a previous storage format version to the latest storage format version.

Bump the major component of LATEST_VERSION and set the minor component to zero.
Create a new version of the modified struct(s), and re-alias the latest version to this new struct (i.e. point Foo to FooV_latest). Move the comments to the newly created struct, and drop visibility if needed.
Implement From<OldVersion> for NewVersion for their new version, e.g. implement From<FooV2> for Foo, or use the Migrate derive macro.
Update the versioned_type! invocation with the new major version as an open ended range at the start of the list. For example, if the new major version is 4 then change this:
```
versioned_type! {
  2.. => Foo
}
```
to this:
```
versioned_type! {
  4.. => Foo,   // The new struct used for Fxfs 4.x and above
  2.. => FooV2  // The old struct used for Fxfs 2.x and 3.x
}
```
Note that the version and the type name suffix should match.

TypeFingerprint

Due to nesting, we have found that structural changes can accidentally creep in. To mitigate this risk we use the TypeFingerprint trait.

Th trait here is only used in the type_fprint tests and has no impact on production code. It ensures that any structural changes to a versioned type or one of its sub-types (e.g. DeviceRange) will be noticed, providing an additional layer of checking above and beyond our golden image tests. The fingerprint generated is a string designed to capture field names and types, but excludes type names in the case of structs and enums, which allows us to rename Foo to FooV1 without triggering a fingerprint change. This aligns with our aims of ensuring we don't break deserialization without being overly strict and triggering on superficial renames.

All supported major version of any “versioned_type” must implement the TypeFingerprint trait. When adding a new version, copy the type_fprint_latest_version test and rename it type_fprint_vXX. You will have to rename the types within the test as well but the fingerprints should not change. This is intended to be relatively painless but we can revise if it becomes problematic or overly verbose.

A failure of this test serves as reminder that the version must be bumped and the string diff should give a rough idea as to what part of a nested type actually changed.

To derive the initial value, add a zero entry to the test in types.rs and run fx test. The failed test will then provide the expected value.

Examples of struct converters

Since these converters are sometimes deleted from the tree (e.g. deleted after a recent breaking change), here are some historical examples of converters:

SuperBlock converter
JournalRecord converter

Breaking changes

Breaking changes are changes where it is not possible (or not practical) to migrate the filesystem from a previous storage format to the latest storage format. For example, switching encryption mechanisms could be a breaking change. These types of changes are expected to be rare.

Update all versioned_type! invocations to drop older versions e.g. change this:
```
versioned_type! {
  4.. => Foo,
  2.. => FooV2
}
```
to simply this:
```
versioned_type! {
  4.. => Foo,
}
```
(Do this for all the structs in types.rs)
Delete any existing From<FooV1> for Foo Fxfs converters in the tree, as we won't need them anymore.
Similarly, delete any old structs (like FooV1).
Bump the major component of LATEST_VERSION and set the minor component to zero.
For any structs being changed in this breaking change, bump their version to match the latest version e.g. if the major component of LATEST_VERSION is now 4, then change this:
```
versioned_type! {
  2.. => Foo,
}
```
to this:
```
versioned_type! {
  4.. => Foo,
}
```
Also bump the version of the SuperBlock to match the major component of LATEST_VERSION e.g. change this:
```
versioned_type! {
  3.. => SuperBlock,
}
```
to this:
```
versioned_type! {
  4.. => SuperBlock,
}
```

When to make breaking changes

There are two main reasons for making breaking changes:

We eventually will want to remove old, unused code. We will do this via an as-yet undefined ‘stepping stone’ process. Devices will be required to upgrade through stepping stone releases of the filesystem at which point we will require a full (major) compaction. This major compaction rewrites all metadata at the latest version for that release. This means we can be sure that versions written two such stepping stones ago will not be in use and can be safely removed.
A rare need to break the on-disk format. e.g. changing checksum algorithm. In such a case we will likely have to write custom code to migrate data structures. The safest way to do this is likely to be to target a single ‘source version’, which also lends itself well to the stepping stone process above. i.e. Migrate to version N as a stepping stone and then N+1 as a second stepping stone.

Any attempt to load a version too low to be supported will result in a runtime error explaining the unsupported version.

Golden Images

Golden images exist under “//src/storage/fxfs/testdata/”. They are small (<10kB), compressed fxfs images from various versions of the filesystem.

The images are generated via the command fx fxfs create_golden (for which code lives under fxfs/tools/src/).

A host test loads the images and ensures that they can all be read. The test also ensures that there is an image for the current LATEST_VERSION. This test is part of CQ and will instruct the user to generate a new image if the version is bumped without also generating one in the same CL.

Golden images are expected to exist until the versions they use are no longer supported at which time they can simply be deleted from the testdata directory.