User:Mstone/Commentaries/olpc-update

This is a commentary intended to elucidate the data structures used by olpcrd and olpc-update in Early boot and how those data structures differ between unpartitioned and partitioned systems.

Requirements

1. We want to be able to store multiple trees of files.
   1. On unpartitioned systems, these file trees should share common data, e.g. via hardlinks or content-addressible storage.
2. At all times, we want to distinguish the file tree that we want to boot on next reboot. Call this tree the "primary" tree.
3. We want to make at least one known-good alternate tree available for rollback upon reboot whenever we have one. Call this the "alternate" tree.
4. OFW needs to be able to find the correct kernel and initramfs.
5. Changes to the assignments of "primary" and "alternate" trees need to be atomic, consistent, and durable with respect to hard power failure.
6. For update purposes, we need to know what tree we booted from.
7. For update purposes, we need a cryptographic manifest for each available tree.

Design for Unpartitioned Machines

Data Structures

1. Multiple trees of files are stored in /versions/pristine.
2. We define a data structure is called a "boot config". Abstractly, each boot config is a struct of pointers to tree-ids.
   • Each boot config is implemented as a directory in /versions/configs containing one to two symlinks named "current" and, optionally, "alt".
3. We identify a distinguished boot config as the target of a symlink at /versions/boot.
4. To atomically modify the distinguished boot config:
   1. making a fresh boot config,
   2. making a fresh symlink pointing to it
   3. renaming the freshly created symlink to /versions/boot
5. Our initramfs puts a symlink at /versions/running to identify the currently running tree.
6. For update purposes, we need to maintain cryptographic manifests of our trees of files. These go in /versions/contents/...

Robust Updates

Automatic updates require sufficient free space to install the update. We get that space by

1. Making and installing a new boot config with no fallback, thereby unreferencing any non-sticky old builds.
2. Deleting any non-sticky old builds.
3. Installing the update.
4. Verifying the update.
5. Making and installing a new boot config with our current running tree as the "alt" image and with the new tree as the "current" image.

This way, the system is *always* in a consistent state.

Design for Partitioned Machines

Data Structures

The design for partitioned systems is simpler than for unpartitioned systems. It works as follows.

1. Partitions are identified by colon-delimited prefixes, like boot:, root:, and so on.
2. At all times, for all tree-ids $a:
   1. boot:/boot should be a symlink to 'boot-versions/$a'
   2. boot:/boot-versions/$a should contain:
      1. a symlink named alt pointing to ../$b for some tree-id $b
      2. the contents of $root:/boot for some other partition $root:
      3. possibly some other unspecified metadata

Robust Updates

Assume that boot:/boot currently points to boot-versions/$r. Then the boot:/boot-versions/$r/alt symlink may be made to loop by being made to point to ../$r in order to preserve the alt invariant while updating, when no consistent alternate data may be available.

After the partition update is verified complete, when consistent alternate data become available, the new boot configuration may be made visible by

1. filling out a new directory boot:/boot-versions/$u
2. making a new symlink in boot:/ pointing to boot-versions/$u
3. renaming it on top of boot:/boot