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

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.

When consistent alternate data become available, after the partition update is verified complete, 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