User:Mstone/Commentaries/olpc-update: Difference between revisions

From OLPC
Jump to navigation Jump to search
mNo edit summary
Line 1: Line 1:
This is a commentary intended to elucidate the data structures used by olpcrd and olpc-update in [[Early boot]].
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.


= Unpartitioned =
= Requirements =

# We want to be able to store multiple trees of files.
## On unpartitioned systems, these file trees should share common data, e.g. via hardlinks or content-addressible storage.
# At all times, we want to distinguish the file tree that we want to boot on next reboot.
#* Call this tree the "primary" tree.
# 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.
# OFW needs to be able to find the correct kernel and initramfs.
# Changes to the assignments of "primary" and "alternate" trees need to be atomic, consistent, and durable with respect to hard power failure.
# For update purposes, we need to know what tree we booted from.
# For update purposes, we need a cryptographic manifest for each available tree.

= Design for Unpartitioned Machines =


== Data Structures ==
== Data Structures ==


# Multiple trees of files are stored in <tt>/versions/pristine</tt>.
# 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.
# This data structure is called a "boot config", and is implemented as a directory in <tt>/versions/configs</tt> containing some symlinks.
# 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 <tt>/versions/configs</tt> containing one to two symlinks named "current" and, optionally, "alt".
# 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 <tt>/versions/boot</tt>.
# We identify a distinguished boot config as the target of a symlink at <tt>/versions/boot</tt>.
# We need to be able to atomically modify the distinguished boot configuration. We do this by
# To atomically modify the distinguished boot config:
## making a fresh boot config,
## making a fresh boot config,
## making a fresh symlink pointing to it
## making a fresh symlink pointing to it
## renaming the freshly created symlink to <tt>/versions/boot</tt>
## renaming the freshly created symlink to <tt>/versions/boot</tt>
# For update purposes, we need to know what actual *tree* is currently running. Therefore, our initramfs puts a symlink at <tt>/versions/running</tt> to identify the currently running *tree*.
# Our initramfs puts a symlink at <tt>/versions/running</tt> to identify the currently running tree.
# For update purposes, we need to maintain cryptographic manifests of our trees of files. These go in <tt>/versions/contents/...</tt>
# For update purposes, we need to maintain cryptographic manifests of our trees of files. These go in <tt>/versions/contents/...</tt>


Line 27: Line 41:
This way, the system is *always* in a consistent state.
This way, the system is *always* in a consistent state.


= Partitioned =
= Design for Partitioned Machines =


== Data Structures ==
== Data Structures ==

Revision as of 15:49, 5 November 2009

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