User:Mstone/Commentaries/olpc-update

This is a commentary intended to elucidate the data structures used by olpcrd and olpc-update in Early boot.

Unpartitioned

Data Structures

1. For rollback purposes, we need a data structure with some pointers in it. (e.g., "current", and usually "alt".) The pointers should point to trees of files.
2. This data structure is called a "boot config", and is implemented as a directory in /versions/configs containing some symlinks.
3. We need a distinguished boot config so that OFW has something specific to hand control to. This distinguished boot config is the target of another pointer implemented as a symlink at /versions/boot.
4. We need to be able to atomically modify the distinguished boot configuration. We do this by
   1. making a fresh boot config,
   2. making a fresh symlink pointing to it
   3. renaming the freshly created symlink to /versions/boot
5. For update purposes, we need to know what actual *tree* is currently running. Therefore, 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.

Partitioned

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

Updating the boot configuration is accomplished 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

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