[ostree/wip/delta: 44/44] WIP static deltas



commit dd67c02cfdddd00f3896a3d3504b8105218687de
Author: Colin Walters <walters verbum org>
Date:   Thu Aug 15 09:17:37 2013 -0400

    WIP static deltas

 Makefile-libostree.am                              |    4 +
 Makefile-ostree.am                                 |    1 +
 src/libostree/README-deltas.md                     |  174 +++++++++
 src/libostree/ostree-core.c                        |   58 +++-
 src/libostree/ostree-core.h                        |    9 +
 src/libostree/ostree-repo-private.h                |    2 +
 src/libostree/ostree-repo-pull.c                   |   53 +++-
 .../ostree-repo-static-delta-compilation.c         |  375 ++++++++++++++++++++
 src/libostree/ostree-repo-static-delta-core.c      |  253 +++++++++++++
 src/libostree/ostree-repo-static-delta-private.h   |   58 +++
 .../ostree-repo-static-delta-processing.c          |  352 ++++++++++++++++++
 src/libostree/ostree-repo.c                        |    2 +
 src/libostree/ostree-repo.h                        |   31 ++
 src/ostree/main.c                                  |    1 +
 src/ostree/ot-builtin-static-delta.c               |  123 +++++++
 src/ostree/ot-builtins.h                           |    1 +
 tests/test-delta.sh                                |   70 ++++
 17 files changed, 1549 insertions(+), 18 deletions(-)
---
diff --git a/Makefile-libostree.am b/Makefile-libostree.am
index 5034c50..48d69b5 100644
--- a/Makefile-libostree.am
+++ b/Makefile-libostree.am
@@ -44,6 +44,10 @@ libostree_1_la_SOURCES = \
        src/libostree/ostree-repo-file.c \
        src/libostree/ostree-repo-file-enumerator.c \
        src/libostree/ostree-repo-file-enumerator.h \
+       src/libostree/ostree-repo-static-delta-core.c \
+       src/libostree/ostree-repo-static-delta-processing.c \
+       src/libostree/ostree-repo-static-delta-compilation.c \
+       src/libostree/ostree-repo-static-delta-private.h \
        $(NULL)
 if USE_LIBARCHIVE
 libostree_1_la_SOURCES += src/libostree/ostree-libarchive-input-stream.h \
diff --git a/Makefile-ostree.am b/Makefile-ostree.am
index 4cdde46..839ac3f 100644
--- a/Makefile-ostree.am
+++ b/Makefile-ostree.am
@@ -39,6 +39,7 @@ ostree_SOURCES = src/ostree/main.c \
        src/ostree/ot-builtin-reset.c \
        src/ostree/ot-builtin-rev-parse.c \
        src/ostree/ot-builtin-show.c \
+       src/ostree/ot-builtin-static-delta.c \
        src/ostree/ot-builtin-write-refs.c \
        src/ostree/ot-main.h \
        src/ostree/ot-main.c \
diff --git a/src/libostree/README-deltas.md b/src/libostree/README-deltas.md
new file mode 100644
index 0000000..ccdda81
--- /dev/null
+++ b/src/libostree/README-deltas.md
@@ -0,0 +1,174 @@
+OSTree Static Object Deltas
+===========================
+
+Currently, OSTree's "archive-z2" mode stores both metadata and content
+objects as individual files in the filesystem.  Content objects are
+zlib-compressed.
+
+The advantage of this is model are:
+
+0) It's easy to understand and implement
+1) Can be served directly over plain HTTP by a static webserver
+2) Space efficient on the server
+
+However, it can be inefficient both for large updates and small ones:
+
+0) For large tree changes (such as going from -runtime to
+   -devel-debug, or major version upgrades), this can mean thousands
+   and thousands of HTTP requests.  The overhead for that is very
+   large (until SPDY/HTTP2.0), and will be catastrophically bad if the
+   webserver is not configured with KeepAlive.
+1) Small changes (typo in gnome-shell .js file) still require around
+   5 metadata HTTP requests, plus a redownload of the whole file.
+
+Why not smart servers?
+======================
+
+Smart servers (custom daemons, or just CGI scripts) as git has are not
+under consideration for this proposal.  OSTree is designed for the
+same use case as GNU/Linux distribution package systems are, where
+content is served by a network of volunteer mirrors that will
+generally not run custom code.
+
+In particular, Amazon S3 style dumb content servers is a very
+important use case, as is being able to apply updates from static
+media like DVD-ROM.
+
+Delta Bytecode Format
+=====================
+
+When a client wants to retrieve commit ${new} while currently running
+${current}, it makes a HTTP request for
+${repo}/deltas/${current}-${new}.delta.  If it exists, then it is
+retrieved and executed.  Otherwise, simply fall back to plain object
+retrieval.
+
+A .delta object is a custom binary format.  It has the following high
+level form:
+
+delta-descriptor:
+  metadata strings: a(ss)
+  metadata binary: a(say)
+  ARRAY[(csum from, csum to)]: ay
+  ARRAY[delta-part-header]
+
+The metadata would include things like a version number, as well as
+extended verification data like a GPG signature.
+
+The second array is an array of delta objects that should be fetched
+and applied before this one.  This is a fairly generic recursion
+mechanism that would potentially allow saving significant storage
+space on the server.
+
+Each delta-part-header is:
+
+  ay checksum
+  guint64 size  /* Size of delta */
+  guint64 usize  /* Uncompressed object size */
+  ARRAY[(guint8 objtype, csum object)]
+
+The checksum is of the delta payload, and each entry in the array
+represents an OSTree object which will be created by the deltapart.
+
+A delta-part has the following form:
+
+byte compression-type (0 = none, 'g' = gzip, 'x' = 'xz')
+delta-part-content
+
+delta-part-content:
+  byte[] payload
+  ARRAY[operation]
+
+The rationale for having delta-part is that it allows easy incremental
+resumption of downloads.  The client can look at the delta descriptor
+and skip downloading delta-parts for which it already has the
+contained objects.  This is better than simply resuming a gigantic
+file because if the client decides to fetch a slightly newer version,
+it's very probable that some of the downloading we've already done is
+still useful.
+
+The delta part is effectively a high level bytecode for a
+stack-oriented machine.  It iterates on the array of objects in order.
+The following operations are available:
+
+FETCH
+  Fall back to fetching the current object individually.  Move
+  to the next object.
+
+WRITE(array[(varint offset, varint length)])
+  Write from current input target (default payload) to output.
+
+GUNZIP(array[(varint offset, varint length)])
+  gunzip from current input target (default payload) to output.
+
+CLOSE
+  Close the current output target, and proceed to the next; if the
+  output object was a temporary, the output resets to the current
+  object.
+
+# Change the input source to an object
+READOBJECT(csum object)
+  Set object as current input target
+
+# Change the input source to payload
+READPAYLOAD
+  Set payload as current input target
+
+Compiling Deltas
+================
+
+After reading the above, you may be wondering how we actually *make*
+these deltas.  I envison a strategy similar to that employed by
+Chromium autoupdate:
+http://www.chromium.org/chromium-os/chromiumos-design-docs/autoupdate-details
+
+Something like this would be a useful initial algorithm:
+1) Compute the set of added objects NEW
+2) For each object in NEW:
+  - Look for a the set of "superficially similar" objects in the
+    previous tree, using heuristics based first on filename (including
+    prefix), then on size.  Call this set CANDIDATES.
+    For each entry in CANDIDATES:
+      - Try doing a bup/librsync style rolling checksum, and compute the
+        list of changed blocks.
+      - Try gzip-compressing it
+3) Choose the lowest cost method for each NEW object, and partition
+   the program for each method into deltapart-sized chunks.
+
+However, there are many other possibilities, that could be used in a
+hybrid mode with the above.  For example, we could try to find similar
+objects, and gzip them together.  This would be a *very* useful
+strategy for things like the 9000 Boost headers which have massive
+amounts of redundant data.
+
+Notice too that the delta format supports falling back to retrieving
+individual objects.  For cases like the initramfs which is compressed
+inside the tree with gzip, we're not going to find an efficient way to
+sync it, so the delta compiler should just fall back to fetching it
+individually.
+
+Which Deltas To Create?
+=======================
+
+Going back to the start, there are two cases to optimize for:
+
+1) Incremental upgrades between builds
+2) Major version upgrades
+
+A command line operation would look something like this:
+
+$ ostree --repo=/path/to/repo gendelta --ref-prefix=gnome-ostree/buildmaster/ --strategy=latest --depth=5
+
+This would tell ostree to generate deltas from each of the last 4
+commits to each ref (e.g. gnome-ostree/buildmaster/x86_64-runtime) to
+the latest commit.  It might also be possible of course to have
+--strategy=incremental where we generate a delta between each commit.
+I suspect that'd be something to do if one has a *lot* of disk space
+to spend, and there's a reason for clients to be fetching individual
+refs.
+
+$ ostree --repo=/path/to/repo gendelta --from=gnome-ostree/3.10/x86_64-runtime 
--to=gnome-ostree/buildmaster/x86_64-runtime
+
+This is an obvious one - generate a delta from the last stable release
+to the current development head.
+
diff --git a/src/libostree/ostree-core.c b/src/libostree/ostree-core.c
index 4303157..70fbaed 100644
--- a/src/libostree/ostree-core.c
+++ b/src/libostree/ostree-core.c
@@ -1339,13 +1339,42 @@ ostree_checksum_from_bytes_v (GVariant *csum_v)
  * ostree_checksum_bytes_peek:
  * @bytes: #GVariant of type ay
  *
- * Returns: (transfer none): Binary checksum data in @bytes; do not free
+ * Returns: (transfer none) (array element-type guint8 fixed-size=32): Binary checksum data in @bytes; do 
not free.  If @bytes does not have the correct length, return %NULL.
  */
 const guchar *
 ostree_checksum_bytes_peek (GVariant *bytes)
 {
   gsize n_elts;
-  return g_variant_get_fixed_array (bytes, &n_elts, 1);
+  const guchar *ret;
+  ret = g_variant_get_fixed_array (bytes, &n_elts, 1);
+  if (G_UNLIKELY (n_elts != 32))
+    return NULL;
+  return ret;
+}
+
+/**
+ * ostree_checksum_bytes_peek_validate:
+ * @bytes: #GVariant of type ay
+ * @error: Errror
+ *
+ * Like ostree_checksum_bytes_peek(), but also throws @error.
+ *
+ * Returns: (transfer none) (array element-type guint8 fixed-size=32): Binary checksum data
+ */
+const guchar *
+ostree_checksum_bytes_peek_validate (GVariant  *bytes,
+                                     GError   **error)
+{
+  const guchar *ret = ostree_checksum_bytes_peek (bytes);
+  if (G_UNLIKELY (!ret))
+    {
+      g_set_error (error, G_IO_ERROR, G_IO_ERROR_FAILED,
+                   "Invalid checksum of length %" G_GUINT64_FORMAT
+                   " expected 32", (guint64) g_variant_n_children (bytes));
+      return FALSE;
+    }
+  return TRUE;
+  
 }
 
 /**
@@ -1378,6 +1407,21 @@ ostree_get_relative_object_path (const char         *checksum,
   return g_string_free (path, FALSE);
 }
 
+char *
+ostree_get_relative_static_delta_path (const char        *from,
+                                       const char        *to)
+{
+  return g_strdup_printf ("deltas/%s-%s/meta", from, to);
+}
+
+char *
+ostree_get_relative_static_delta_part_path (const char        *from,
+                                            const char        *to,
+                                            guint              i)
+{
+  return g_strdup_printf ("deltas/%s-%s/%u", from, to, i);
+}
+
 /**
  * ostree_file_header_parse:
  * @metadata: A metadata variant of type %OSTREE_FILE_HEADER_GVARIANT_FORMAT
@@ -1787,15 +1831,7 @@ gboolean
 ostree_validate_structureof_csum_v (GVariant  *checksum,
                                     GError   **error)
 {
-  gsize n_children = g_variant_n_children (checksum);
-  if (n_children != 32)
-    {
-      g_set_error (error, G_IO_ERROR, G_IO_ERROR_FAILED,
-                   "Invalid checksum of length %" G_GUINT64_FORMAT
-                   " expected 32", (guint64) n_children);
-      return FALSE;
-    }
-  return TRUE;
+  return ostree_checksum_bytes_peek_validate (checksum, error) != NULL;
 }
 
 /**
diff --git a/src/libostree/ostree-core.h b/src/libostree/ostree-core.h
index 253be08..d82d288 100644
--- a/src/libostree/ostree-core.h
+++ b/src/libostree/ostree-core.h
@@ -162,6 +162,8 @@ void ostree_checksum_inplace_to_bytes (const char *checksum,
 
 const guchar *ostree_checksum_bytes_peek (GVariant *bytes);
 
+const guchar *ostree_checksum_bytes_peek_validate (GVariant *bytes, GError **error);
+
 int ostree_cmp_checksum_bytes (const guchar *a, const guchar *b);
 
 gboolean ostree_validate_rev (const char *rev, GError **error);
@@ -197,6 +199,13 @@ char *ostree_get_relative_object_path (const char        *checksum,
                                        OstreeObjectType   type,
                                        gboolean           compressed);
 
+char *ostree_get_relative_static_delta_path (const char        *from,
+                                             const char        *to);
+
+char *ostree_get_relative_static_delta_part_path (const char        *from,
+                                                  const char        *to,
+                                                  guint              i);
+
 gboolean ostree_get_xattrs_for_file (GFile         *f,
                                      GVariant     **out_xattrs,
                                      GCancellable  *cancellable,
diff --git a/src/libostree/ostree-repo-private.h b/src/libostree/ostree-repo-private.h
index e03656d..3fdf977 100644
--- a/src/libostree/ostree-repo-private.h
+++ b/src/libostree/ostree-repo-private.h
@@ -33,6 +33,7 @@ struct OstreeRepo {
   GFile *local_heads_dir;
   GFile *remote_heads_dir;
   GFile *objects_dir;
+  GFile *deltas_dir;
   GFile *uncompressed_objects_dir;
   GFile *remote_cache_dir;
   GFile *config_file;
@@ -82,5 +83,6 @@ _ostree_repo_stage_directory_meta (OstreeRepo   *self,
                                    GCancellable *cancellable,
                                    GError      **error);
 
+
 G_END_DECLS
 
diff --git a/src/libostree/ostree-repo-pull.c b/src/libostree/ostree-repo-pull.c
index 90cdbee..472f61b 100644
--- a/src/libostree/ostree-repo-pull.c
+++ b/src/libostree/ostree-repo-pull.c
@@ -1130,6 +1130,49 @@ load_remote_repo_config (OtPullData    *pull_data,
   return ret;
 }
 
+static void
+initiate_commit_scan (OtPullData   *pull_data,
+                      const char   *checksum)
+{
+  ot_waitable_queue_push (pull_data->metadata_objects_to_scan,
+                          pull_worker_message_new (PULL_MSG_SCAN,
+                                                   ostree_object_name_serialize (checksum, 
OSTREE_OBJECT_TYPE_COMMIT)));
+}
+
+static gboolean
+request_static_delta (OtPullData  *pull_data,
+                      const char  *ref,
+                      const char  *checksum,
+                      GError     **error)
+{
+  gboolean ret = FALSE;
+  gs_free char *from_revision = NULL;
+  SoupURI *target_uri = NULL;
+
+  if (!ostree_repo_resolve_rev (pull_data->repo, ref, TRUE, &from_revision, error))
+    goto out;
+
+  if (from_revision == NULL)
+    {
+      initiate_commit_scan (pull_data, checksum);
+    }
+  else
+    {
+      gs_free char *delta_name = ostree_get_relative_static_delta_path (from_revision, checksum);
+      gs_unref_object GFile *delta_descriptor = NULL;
+
+      target_uri = suburi_new (pull_data->base_uri, delta_name, NULL);
+
+      if (!fetch_uri (pull_data, target_uri, "delta-", &delta_descriptor,
+                      pull_data->cancellable, error))
+        goto out;
+    }
+  
+  ret = TRUE;
+ out:
+  return ret;
+}
+
 gboolean
 ostree_repo_pull (OstreeRepo               *self,
                   const char               *remote_name,
@@ -1315,10 +1358,7 @@ ostree_repo_pull (OstreeRepo               *self,
   while (g_hash_table_iter_next (&hash_iter, &key, &value))
     {
       const char *commit = value;
-
-      ot_waitable_queue_push (pull_data->metadata_objects_to_scan,
-                              pull_worker_message_new (PULL_MSG_SCAN,
-                                                       ostree_object_name_serialize (commit, 
OSTREE_OBJECT_TYPE_COMMIT)));
+      initiate_commit_scan (pull_data, commit);
     }
 
   g_hash_table_iter_init (&hash_iter, requested_refs_to_fetch);
@@ -1330,9 +1370,8 @@ ostree_repo_pull (OstreeRepo               *self,
       gs_free char *remote_ref = NULL;
       gs_free char *baseurl = NULL;
 
-      ot_waitable_queue_push (pull_data->metadata_objects_to_scan,
-                              pull_worker_message_new (PULL_MSG_SCAN,
-                                                       ostree_object_name_serialize (sha256, 
OSTREE_OBJECT_TYPE_COMMIT)));
+      if (!request_static_delta (pull_data, ref, sha256, error))
+        goto out;
       g_hash_table_insert (updated_refs, g_strdup (ref), g_strdup (sha256));
     }
   
diff --git a/src/libostree/ostree-repo-static-delta-compilation.c 
b/src/libostree/ostree-repo-static-delta-compilation.c
new file mode 100644
index 0000000..5967603
--- /dev/null
+++ b/src/libostree/ostree-repo-static-delta-compilation.c
@@ -0,0 +1,375 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * Copyright (C) 2013 Colin Walters <walters verbum org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include <string.h>
+
+#include "ostree-repo-private.h"
+#include "ostree-repo-static-delta-private.h"
+#include "ostree-diff.h"
+#include "otutil.h"
+#include "ostree-varint.h"
+
+typedef struct {
+  guint64 uncompressed_size;
+  GPtrArray *objects;
+  GString *payload;
+  GString *operations;
+} OstreeStaticDeltaPartBuilder;
+
+typedef struct {
+  GPtrArray *parts;
+} OstreeStaticDeltaBuilder;
+
+static void
+ostree_static_delta_part_builder_unref (OstreeStaticDeltaPartBuilder *part_builder)
+{
+  if (part_builder->objects)
+    g_ptr_array_unref (part_builder->objects);
+  if (part_builder->payload)
+    g_string_free (part_builder->payload, TRUE);
+  if (part_builder->operations)
+    g_string_free (part_builder->operations, TRUE);
+  g_free (part_builder);
+}
+
+static OstreeStaticDeltaPartBuilder *
+allocate_part (OstreeStaticDeltaBuilder *builder)
+{
+  OstreeStaticDeltaPartBuilder *part = g_new0 (OstreeStaticDeltaPartBuilder, 1);
+  part->objects = g_ptr_array_new_with_free_func ((GDestroyNotify)g_variant_unref);
+  part->payload = g_string_new (NULL);
+  part->operations = g_string_new (NULL);
+  part->uncompressed_size = 0;
+  g_ptr_array_add (builder->parts, part);
+  return part;
+}
+
+static GBytes *
+objtype_checksum_array_new (GPtrArray *objects)
+{
+  guint i;
+  GByteArray *ret = g_byte_array_new ();
+
+  for (i = 0; i < objects->len; i++)
+    {
+      GVariant *serialized_key = objects->pdata[i];
+      OstreeObjectType objtype;
+      const char *checksum;
+      guint8 csum[32];
+      guint8 objtype_v;
+        
+      ostree_object_name_deserialize (serialized_key, &checksum, &objtype);
+      objtype_v = (guint8) objtype;
+
+      ostree_checksum_inplace_to_bytes (checksum, csum);
+
+      g_byte_array_append (ret, &objtype_v, 1);
+      g_byte_array_append (ret, csum, sizeof (csum));
+    }
+  return g_byte_array_free_to_bytes (ret);
+}
+
+static gboolean 
+generate_delta_lowlatency (OstreeRepo                       *repo,
+                           const char                       *from,
+                           const char                       *to,
+                           OstreeStaticDeltaBuilder         *builder,
+                           GCancellable                     *cancellable,
+                           GError                          **error)
+{
+  gboolean ret = FALSE;
+  GHashTableIter hashiter;
+  gpointer key, value;
+  OstreeStaticDeltaPartBuilder *current_part = NULL;
+  gs_unref_object GFile *root_from = NULL;
+  gs_unref_object GFile *root_to = NULL;
+  gs_unref_ptrarray GPtrArray *modified = NULL;
+  gs_unref_ptrarray GPtrArray *removed = NULL;
+  gs_unref_ptrarray GPtrArray *added = NULL;
+  gs_unref_hashtable GHashTable *to_reachable_objects = NULL;
+  gs_unref_hashtable GHashTable *from_reachable_objects = NULL;
+  gs_unref_hashtable GHashTable *new_reachable_objects = NULL;
+
+  if (!ostree_repo_read_commit (repo, from, &root_from, cancellable, error))
+    goto out;
+  if (!ostree_repo_read_commit (repo, to, &root_to, cancellable, error))
+    goto out;
+
+  /* Gather a filesystem level diff; when we do heuristics to ship
+   * just parts of changed files, we can make use of this data.
+   */
+  modified = g_ptr_array_new_with_free_func ((GDestroyNotify) ostree_diff_item_unref);
+  removed = g_ptr_array_new_with_free_func ((GDestroyNotify) g_object_unref);
+  added = g_ptr_array_new_with_free_func ((GDestroyNotify) g_object_unref);
+  if (!ostree_diff_dirs (root_from, root_to, modified, removed, added,
+                         cancellable, error))
+    goto out;
+
+  from_reachable_objects = ostree_repo_traverse_new_reachable ();
+  if (!ostree_repo_traverse_commit (repo, from, -1, from_reachable_objects,
+                                    cancellable, error))
+    goto out;
+
+  to_reachable_objects = ostree_repo_traverse_new_reachable ();
+  if (!ostree_repo_traverse_commit (repo, to, -1, to_reachable_objects,
+                                    cancellable, error))
+    goto out;
+
+  new_reachable_objects = ostree_repo_traverse_new_reachable ();
+
+  g_hash_table_iter_init (&hashiter, to_reachable_objects);
+  while (g_hash_table_iter_next (&hashiter, &key, &value))
+    {
+      GVariant *serialized_key = key;
+
+      if (g_hash_table_contains (from_reachable_objects, serialized_key))
+        continue;
+
+      g_hash_table_insert (new_reachable_objects, g_variant_ref (serialized_key), serialized_key);
+    }
+
+  current_part = allocate_part (builder);
+
+  g_hash_table_iter_init (&hashiter, new_reachable_objects);
+  while (g_hash_table_iter_next (&hashiter, &key, &value))
+    {
+      GVariant *serialized_key = key;
+      const char *checksum;
+      OstreeObjectType objtype;
+      guint64 content_size;
+      gs_unref_object GInputStream *content_stream = NULL;
+      gsize bytes_read;
+      gsize object_payload_start;
+      const guint readlen = 4096;
+
+      ostree_object_name_deserialize (serialized_key, &checksum, &objtype);
+
+      if (!ostree_repo_load_object_stream (repo, objtype, checksum,
+                                           &content_stream, &content_size,
+                                           cancellable, error))
+        goto out;
+
+      current_part->uncompressed_size += content_size;
+
+      /* Ensure we have at least one object per delta, even if a given
+       * object is larger.
+       */
+      if (current_part->objects->len > 0 &&
+          current_part->payload->len + content_size > OSTREE_STATIC_DELTA_PART_MAX_SIZE_BYTES)
+        {
+          current_part = allocate_part (builder);
+        } 
+
+      object_payload_start = current_part->payload->len;
+
+      g_ptr_array_add (current_part->objects, g_variant_ref (serialized_key));
+
+      while (TRUE)
+        {
+          gsize empty_space;
+
+          empty_space = current_part->payload->allocated_len - current_part->payload->len;
+          if (empty_space < readlen)
+            {
+              gsize origlen;
+              origlen = current_part->payload->len;
+              g_string_set_size (current_part->payload, current_part->payload->allocated_len + (readlen - 
empty_space));
+              current_part->payload->len = origlen;
+            }
+
+          if (!g_input_stream_read_all (content_stream,
+                                        current_part->payload->str + current_part->payload->len,
+                                        readlen,
+                                        &bytes_read,
+                                        cancellable, error))
+            goto out;
+          if (bytes_read == 0)
+            break;
+          current_part->payload->len += bytes_read;
+
+          g_string_append_c (current_part->operations, (gchar)OSTREE_STATIC_DELTA_OP_WRITE);
+          g_string_append_c (current_part->operations, (gchar)1);
+          _ostree_write_varuint64 (current_part->operations, object_payload_start);
+          _ostree_write_varuint64 (current_part->operations, current_part->payload->len - 
object_payload_start);
+          g_string_append_c (current_part->operations, (gchar)OSTREE_STATIC_DELTA_OP_CLOSE);
+        }
+    }
+
+  ret = TRUE;
+ out:
+  return ret;
+}
+
+/**
+ * ostree_repo_static_delta_generate:
+ * @self: Repo
+ * @opt: High level optimization choice
+ * @from: ASCII SHA256 checksum of origin
+ * @to: ASCII SHA256 checksum of target
+ * @metadata: (allow-none): Optional metadata
+ * @cancellable: Cancellable
+ * @error: Error
+ *
+ * Generate a lookaside "static delta" from @from which can generate
+ * the objects in @to.  This delta is an optimization over fetching
+ * individual objects, and can be conveniently stored and applied
+ * offline.
+ */
+gboolean
+ostree_repo_static_delta_generate (OstreeRepo                   *self,
+                                   OstreeStaticDeltaGenerateOpt  opt,
+                                   const char                   *from,
+                                   const char                   *to,
+                                   GVariant                     *metadata,
+                                   GCancellable                 *cancellable,
+                                   GError                      **error)
+{
+  gboolean ret = FALSE;
+  OstreeStaticDeltaBuilder builder = { 0, };
+  guint i;
+  GVariant *metadata_source;
+  gs_unref_variant_builder GVariantBuilder *part_headers = NULL;
+  gs_unref_ptrarray GPtrArray *part_tempfiles = NULL;
+  gs_unref_variant GVariant *delta_descriptor = NULL;
+  gs_free char *descriptor_relpath = NULL;
+  gs_unref_object GFile *descriptor_path = NULL;
+  gs_unref_object GFile *descriptor_dir = NULL;
+  gs_unref_variant GVariant *tmp_metadata = NULL;
+
+  builder.parts = g_ptr_array_new_with_free_func ((GDestroyNotify)ostree_static_delta_part_builder_unref);
+
+  /* Ignore optimization flags */
+  if (!generate_delta_lowlatency (self, from, to, &builder,
+                                  cancellable, error))
+    goto out;
+
+  part_headers = g_variant_builder_new (G_VARIANT_TYPE ("a" OSTREE_STATIC_DELTA_PART_HEADER_FORMAT));
+  part_tempfiles = g_ptr_array_new_with_free_func (g_object_unref);
+  for (i = 0; i < builder.parts->len; i++)
+    {
+      OstreeStaticDeltaPartBuilder *part_builder = builder.parts->pdata[i];
+      GBytes *payload_b;
+      GBytes *operations_b;
+      gs_free guchar *part_checksum = NULL;
+      gs_free_checksum GChecksum *checksum = NULL;
+      gs_unref_bytes GBytes *objtype_checksum_array = NULL;
+      gs_unref_object GFile *part_tempfile = NULL;
+      gs_unref_object GOutputStream *part_temp_outstream = NULL;
+      gs_unref_object GInputStream *part_in = NULL;
+      gs_unref_object GInputStream *part_payload_in = NULL;
+      gs_unref_object GMemoryOutputStream *part_payload_out = NULL;
+      gs_unref_object GConverterOutputStream *part_payload_compressor = NULL;
+      gs_unref_object GConverter *zlib_compressor = NULL;
+      gs_unref_variant GVariant *delta_part_content = NULL;
+      gs_unref_variant GVariant *delta_part = NULL;
+      gs_unref_variant GVariant *delta_part_header = NULL;
+
+      payload_b = g_string_free_to_bytes (part_builder->payload);
+      part_builder->payload = NULL;
+      
+      operations_b = g_string_free_to_bytes (part_builder->operations);
+      part_builder->operations = NULL;
+      /* FIXME - avoid duplicating memory here */
+      delta_part_content = g_variant_new ("(@ay ay)",
+                                          ot_gvariant_new_ay_bytes (payload_b),
+                                          ot_gvariant_new_ay_bytes (operations_b));
+      g_variant_ref_sink (delta_part_content);
+
+      /* Hardcode gzip for now */
+      zlib_compressor = (GConverter*)g_zlib_compressor_new (G_ZLIB_COMPRESSOR_FORMAT_RAW, 9);
+      part_payload_in = ot_variant_read (delta_part_content);
+      part_payload_out = (GMemoryOutputStream*)g_memory_output_stream_new_resizable ();
+      part_payload_compressor = (GConverterOutputStream*)g_converter_output_stream_new 
((GOutputStream*)part_payload_out, zlib_compressor);
+
+      if (0 > g_output_stream_splice ((GOutputStream*)part_payload_compressor, part_payload_in,
+                                      G_OUTPUT_STREAM_SPLICE_CLOSE_TARGET | 
G_OUTPUT_STREAM_SPLICE_CLOSE_SOURCE,
+                                      cancellable, error))
+        goto out;
+
+      /* FIXME - avoid duplicating memory here */
+      delta_part = g_variant_new ("(y ay)",
+                                  (guint8)'g',
+                                  ot_gvariant_new_ay_bytes (g_memory_output_stream_steal_as_bytes 
(part_payload_out)));
+
+      if (!gs_file_open_in_tmpdir (self->tmp_dir, 0644,
+                                   &part_tempfile, &part_temp_outstream,
+                                   cancellable, error))
+        goto out;
+      part_in = ot_variant_read (delta_part);
+      if (!ot_gio_splice_get_checksum (part_temp_outstream, part_in,
+                                       &part_checksum,
+                                       cancellable, error))
+        goto out;
+
+      objtype_checksum_array = objtype_checksum_array_new (part_builder->objects);
+      delta_part_header = g_variant_new ("(@ayttay)",
+                                         ot_gvariant_new_ay_bytes (objtype_checksum_array),
+                                         g_variant_get_size (delta_part),
+                                         part_builder->uncompressed_size,
+                                         g_variant_builder_new (G_VARIANT_TYPE ("ay")));
+      g_variant_builder_add_value (part_headers, g_variant_ref (delta_part_header));
+      g_ptr_array_add (part_tempfiles, g_object_ref (part_tempfile));
+    }
+
+  descriptor_relpath = ostree_get_relative_static_delta_path (from, to);
+  descriptor_path = g_file_resolve_relative_path (self->repodir, descriptor_relpath);
+  descriptor_dir = g_file_get_parent (descriptor_path);
+
+  if (!gs_file_ensure_directory (descriptor_dir, TRUE, cancellable, error))
+    goto out;
+
+  for (i = 0; i < builder.parts->len; i++)
+    {
+      GFile *tempfile = part_tempfiles->pdata[i];
+      gs_free char *part_relpath = ostree_get_relative_static_delta_part_path (from, to, i);
+      gs_unref_object GFile *part_path = g_file_resolve_relative_path (self->repodir, part_relpath);
+
+      if (!gs_file_rename (tempfile, part_path, cancellable, error))
+        goto out;
+    }
+
+  if (metadata != NULL)
+    metadata_source = metadata;
+  else
+    {
+      GVariantBuilder tmpbuilder;
+      g_variant_builder_init (&tmpbuilder, G_VARIANT_TYPE ("(a(ss)a(say))"));
+      g_variant_builder_add (&tmpbuilder, "a(ss)", NULL);
+      g_variant_builder_add (&tmpbuilder, "a(say)", NULL);
+      tmp_metadata = g_variant_builder_end (&tmpbuilder);
+      g_variant_ref_sink (tmp_metadata);
+      metadata_source = tmp_metadata;
+    }
+
+  delta_descriptor = g_variant_new ("(@(a(ss)a(say))aya(ayttay))",
+                                    metadata_source,
+                                    g_variant_builder_new (G_VARIANT_TYPE ("ay")),
+                                    part_headers);
+
+  if (!ot_util_variant_save (descriptor_path, delta_descriptor, cancellable, error))
+    goto out;
+
+  ret = TRUE;
+ out:
+  g_clear_pointer (&builder.parts, g_ptr_array_unref);
+  return ret;
+}
diff --git a/src/libostree/ostree-repo-static-delta-core.c b/src/libostree/ostree-repo-static-delta-core.c
new file mode 100644
index 0000000..c4b358e
--- /dev/null
+++ b/src/libostree/ostree-repo-static-delta-core.c
@@ -0,0 +1,253 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * Copyright (C) 2013 Colin Walters <walters verbum org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include "ostree-repo-private.h"
+#include "ostree-repo-static-delta-private.h"
+#include "otutil.h"
+
+gboolean
+_ostree_static_delta_parse_checksum_array (GVariant      *array,
+                                           guint8       **out_checksums_array,
+                                           guint         *out_n_checksums,
+                                           GError       **error)
+{
+  gsize n = g_variant_n_children (array);
+  guint n_checksums;
+
+  n_checksums = n / OSTREE_STATIC_DELTA_OBJTYPE_CSUM_LEN;
+
+  if (G_UNLIKELY(n == 0 ||
+                 n > (G_MAXUINT32/OSTREE_STATIC_DELTA_OBJTYPE_CSUM_LEN) ||
+                 (n_checksums * OSTREE_STATIC_DELTA_OBJTYPE_CSUM_LEN) != n))
+    {
+      g_set_error (error, G_IO_ERROR, G_IO_ERROR_FAILED,
+                   "Invalid checksum array length %" G_GSIZE_FORMAT, n);
+      return FALSE;
+    }
+
+  *out_checksums_array = (gpointer)g_variant_get_data (array);
+  *out_n_checksums = n_checksums;
+
+  return TRUE;
+}
+
+
+/**
+ * ostree_repo_list_static_delta_names:
+ * @self: Repo
+ * @out_deltas: (out) (element-type utf8): String name of deltas (checksum-checksum.delta)
+ * @cancellable: Cancellable
+ * @error: Error
+ *
+ * This function synchronously enumerates all static deltas in the
+ * repository, returning its result in @out_deltas.
+ */ 
+gboolean
+ostree_repo_list_static_delta_names (OstreeRepo                  *self,
+                                     GPtrArray                  **out_deltas,
+                                     GCancellable                *cancellable,
+                                     GError                     **error)
+{
+  gboolean ret = FALSE;
+  gs_unref_ptrarray GPtrArray *ret_deltas = NULL;
+  gs_unref_object GFileEnumerator *dir_enum = NULL;
+
+  ret_deltas = g_ptr_array_new_with_free_func (g_free);
+
+  if (g_file_query_exists (self->deltas_dir, NULL))
+    {
+      dir_enum = g_file_enumerate_children (self->deltas_dir, OSTREE_GIO_FAST_QUERYINFO,
+                                            G_FILE_QUERY_INFO_NOFOLLOW_SYMLINKS,
+                                            NULL, error);
+      if (!dir_enum)
+        goto out;
+      
+      while (TRUE)
+        {
+          GFileInfo *file_info;
+          GFile *child;
+          const char *name;
+
+          if (!gs_file_enumerator_iterate (dir_enum, &file_info, &child,
+                                           NULL, error))
+            goto out;
+          if (file_info == NULL)
+            break;
+
+          if (g_file_info_get_file_type (file_info) != G_FILE_TYPE_REGULAR)
+            continue;
+          name = g_file_info_get_name (file_info);
+          if (!g_str_has_suffix (name, ".delta"))
+            continue;
+      
+          g_ptr_array_add (ret_deltas, g_strdup (name));
+        }
+    }
+
+  ret = TRUE;
+  gs_transfer_out_value (out_deltas, &ret_deltas);
+ out:
+  return ret;
+}
+
+static gboolean
+have_all_objects (OstreeRepo             *repo,
+                  GVariant               *checksum_array,
+                  gboolean               *out_have_all,
+                  GCancellable           *cancellable,
+                  GError                **error)
+{
+  gboolean ret = FALSE;
+  guint8 *checksums_data;
+  guint i,n_checksums;
+  gboolean have_object = TRUE;
+
+  if (!_ostree_static_delta_parse_checksum_array (checksum_array,
+                                                  &checksums_data,
+                                                  &n_checksums,
+                                                  error))
+    goto out;
+
+  for (i = 0; i < n_checksums; i++)
+    {
+      guint8 objtype = *checksums_data;
+      const guint8 *csum = checksums_data + 1;
+      char tmp_checksum[65];
+
+      if (G_UNLIKELY(!ostree_validate_structureof_objtype (objtype, error)))
+        goto out;
+
+      ostree_checksum_inplace_from_bytes (csum, tmp_checksum);
+
+      if (!ostree_repo_has_object (repo, (OstreeObjectType) objtype, tmp_checksum,
+                                   &have_object, cancellable, error))
+        goto out;
+
+      if (!have_object)
+        break;
+
+      checksums_data += OSTREE_STATIC_DELTA_OBJTYPE_CSUM_LEN;
+    }
+
+  ret = TRUE;
+  *out_have_all = have_object;
+ out:
+  return ret;
+}
+
+/**
+ * ostree_repo_static_delta_execute_offline:
+ * @self: Repo
+ * @dir: Path to a directory containing static delta data
+ * @skip_validatation: If %TRUE, assume data integrity
+ * @cancellable: Cancellable
+ * @error: Error
+ *
+ * Given a directory representing an already-downloaded static delta
+ * on disk, apply it, generating a new commit.  The directory must be
+ * named with the form "FROM-TO", where both are checksums, and it
+ * must contain a file named "meta", along with at least one part.
+ */
+gboolean
+ostree_repo_static_delta_execute_offline (OstreeRepo                    *self,
+                                          GFile                         *dir,
+                                          gboolean                       skip_validatation,
+                                          GCancellable                  *cancellable,
+                                          GError                      **error)
+{
+  gboolean ret = FALSE;
+  gs_unref_object GFile *meta_file = g_file_get_child (dir, "meta");
+  gs_unref_variant GVariant *meta = NULL;
+  gs_unref_variant GVariant *headers = NULL;
+  guint i, n;
+
+  if (!ot_util_variant_map (meta_file, G_VARIANT_TYPE (OSTREE_STATIC_DELTA_DESCRIPTOR_FORMAT),
+                            FALSE, &meta, error))
+    goto out;
+
+  headers = g_variant_get_child_value (meta, 2);
+  n = g_variant_n_children (headers);
+  for (i = 0; i < n; i++)
+    {
+      guint64 size;
+      guint64 usize;
+      const guchar *csum;
+      gboolean have_all;
+      gs_unref_variant GVariant *header = NULL;
+      gs_unref_variant GVariant *csum_v = NULL;
+      gs_unref_variant GVariant *objects = NULL;
+      gs_unref_object GFile *part_path = NULL;
+      gs_unref_variant GVariant *part = NULL;
+
+      header = g_variant_get_child_value (headers, i);
+      g_variant_get (header, "(@aytt ay)", &csum_v, &size, &usize, &objects);
+
+      if (!have_all_objects (self, objects, &have_all, cancellable, error))
+        goto out;
+
+      /* If we already have these objects, don't bother executing the
+       * static delta.
+       */
+      if (have_all)
+        continue;
+
+      csum = ostree_checksum_bytes_peek_validate (csum_v, error);
+      if (!csum)
+        goto out;
+
+      part_path = ot_gfile_resolve_path_printf (dir, "%u", i);
+
+      if (!skip_validatation)
+        {
+          gs_free guchar *actual_checksum = NULL;
+          gs_unref_object GInputStream *in = NULL;
+
+          in = (GInputStream*)g_file_read (part_path, cancellable, error);
+          if (!in)
+            goto out;
+
+          if (!ot_gio_checksum_stream (in, &actual_checksum,
+                                       cancellable, error))
+            goto out;
+
+          if (ostree_cmp_checksum_bytes (csum, actual_checksum) != 0)
+            {
+              g_set_error (error, G_IO_ERROR, G_IO_ERROR_FAILED,
+                           "Checksum mismatch in static delta %s part %u",
+                           gs_file_get_path_cached (dir), i);
+              goto out;
+            }
+        }
+
+      if (!ot_util_variant_map (part_path, G_VARIANT_TYPE (OSTREE_STATIC_DELTA_PART_PAYLOAD_FORMAT),
+                                TRUE, &part, error))
+        goto out;
+      
+      if (!_ostree_static_delta_part_execute (self, header, part, cancellable, error))
+        goto out;
+    }
+
+  ret = TRUE;
+ out:
+  return ret;
+}
+
diff --git a/src/libostree/ostree-repo-static-delta-private.h 
b/src/libostree/ostree-repo-static-delta-private.h
new file mode 100644
index 0000000..0e344d2
--- /dev/null
+++ b/src/libostree/ostree-repo-static-delta-private.h
@@ -0,0 +1,58 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * Copyright (C) 2013 Colin Walters <walters verbum org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#pragma once
+
+#include "ostree-core.h"
+
+G_BEGIN_DECLS
+
+/* Arbitrarily chosen */
+#define OSTREE_STATIC_DELTA_PART_MAX_SIZE_BYTES (16*1024*1024)
+/* 1 byte for object type, 32 bytes for checksum */
+#define OSTREE_STATIC_DELTA_OBJTYPE_CSUM_LEN 33
+
+#define OSTREE_STATIC_DELTA_PART_PAYLOAD_FORMAT "(ayay)"
+#define OSTREE_STATIC_DELTA_PART_HEADER_FORMAT "(ayttay)"
+#define OSTREE_STATIC_DELTA_METADATA_FORMAT "(a(ss)a(say))"
+#define OSTREE_STATIC_DELTA_DESCRIPTOR_FORMAT "(" OSTREE_STATIC_DELTA_METADATA_FORMAT "aya" 
OSTREE_STATIC_DELTA_PART_HEADER_FORMAT ")"
+
+gboolean _ostree_static_delta_part_execute (OstreeRepo      *repo,
+                                            GVariant        *header,
+                                            GVariant        *part,
+                                            GCancellable    *cancellable,
+                                            GError         **error);
+
+typedef enum {
+  OSTREE_STATIC_DELTA_OP_FETCH = 1,
+  OSTREE_STATIC_DELTA_OP_WRITE = 2,
+  OSTREE_STATIC_DELTA_OP_GUNZIP = 3,
+  OSTREE_STATIC_DELTA_OP_CLOSE = 4,
+  OSTREE_STATIC_DELTA_OP_READOBJECT = 5,
+  OSTREE_STATIC_DELTA_OP_READPAYLOAD = 6
+} OstreeStaticDeltaOpCode;
+
+gboolean
+_ostree_static_delta_parse_checksum_array (GVariant      *array,
+                                           guint8       **out_checksums_array,
+                                           guint         *out_n_checksums,
+                                           GError       **error);
+G_END_DECLS
+
diff --git a/src/libostree/ostree-repo-static-delta-processing.c 
b/src/libostree/ostree-repo-static-delta-processing.c
new file mode 100644
index 0000000..1ac1b11
--- /dev/null
+++ b/src/libostree/ostree-repo-static-delta-processing.c
@@ -0,0 +1,352 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * Copyright (C) 2013 Colin Walters <walters verbum org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include <string.h>
+
+#include "ostree-repo-private.h"
+#include "ostree-repo-static-delta-private.h"
+#include "otutil.h"
+#include "ostree-varint.h"
+
+/* This should really always be true, but hey, let's just assert it */
+G_STATIC_ASSERT (sizeof (guint) >= sizeof (guint32));
+
+typedef struct {
+  guint           checksum_index;
+  const guint8   *checksums;
+  guint           n_checksums;
+
+  const guint8   *opdata;
+  guint           oplen;
+
+  OstreeObjectType output_objtype;
+  const guint8   *output_target;
+  GFile          *output_tmp_path;
+  GOutputStream  *output_tmp_stream;
+  const guint8   *input_target_csum;
+
+  const guint8   *payload_data;
+  guint64         payload_size; 
+} StaticDeltaExecutionState;
+
+typedef gboolean (*DispatchOpFunc) (OstreeRepo                 *repo,
+                                    StaticDeltaExecutionState  *state,
+                                    GCancellable               *cancellable,
+                                    GError                    **error);
+
+typedef struct  {
+  const char *name;
+  DispatchOpFunc func;
+} OstreeStaticDeltaOperation;
+
+#define OPPROTO(name) \
+  static gboolean dispatch_##name (OstreeRepo                 *repo, \
+                                   StaticDeltaExecutionState  *state, \
+                                   GCancellable               *cancellable, \
+                                   GError                    **error);
+
+OPPROTO(fetch)
+OPPROTO(write)
+OPPROTO(gunzip)
+OPPROTO(close)
+#undef OPPROTO
+
+static OstreeStaticDeltaOperation op_dispatch_table[] = {
+  { "fetch", dispatch_fetch },
+  { "write", dispatch_write },
+  { "gunzip", dispatch_gunzip },
+  { "close", dispatch_close },
+  { NULL }
+};
+
+static gboolean
+open_output_target_csum (OstreeRepo                  *repo,
+                         StaticDeltaExecutionState   *state,
+                         GCancellable                *cancellable,
+                         GError                     **error)
+{
+  gboolean ret = FALSE;
+  guint8 *objcsum;
+
+  g_assert (state->checksums != NULL);
+  g_assert (state->output_target == NULL);
+  g_assert (state->output_tmp_path == NULL);
+  g_assert (state->output_tmp_stream == NULL);
+  g_assert (state->checksum_index < state->n_checksums);
+
+  objcsum = (guint8*)state->checksums + (state->checksum_index * OSTREE_STATIC_DELTA_OBJTYPE_CSUM_LEN);
+
+  if (G_UNLIKELY(!ostree_validate_structureof_objtype (*objcsum, error)))
+    goto out;
+
+  state->output_objtype = (OstreeObjectType) *objcsum;
+  state->output_target = objcsum + 1;
+  if (!gs_file_open_in_tmpdir (repo->tmp_dir, 0644,
+                               &state->output_tmp_path, &state->output_tmp_stream,
+                               cancellable, error))
+    goto out;
+
+  ret = TRUE;
+ out:
+  return ret;
+}
+
+
+gboolean
+_ostree_static_delta_part_execute (OstreeRepo      *repo,
+                                   GVariant        *header,
+                                   GVariant        *part,
+                                   GCancellable    *cancellable,
+                                   GError         **error)
+{
+  gboolean ret = FALSE;
+  guint8 *checksums_data;
+  gs_unref_variant GVariant *checksums = NULL;
+  gs_unref_variant GVariant *payload = NULL;
+  gs_unref_variant GVariant *ops = NULL;
+  StaticDeltaExecutionState statedata = { 0, };
+  StaticDeltaExecutionState *state = &statedata;
+
+  g_variant_get_child (header, 1, "@ay", &checksums);
+  if (!_ostree_static_delta_parse_checksum_array (checksums,
+                                                  &checksums_data,
+                                                  &state->n_checksums,
+                                                  error))
+    goto out;
+
+  state->checksums = checksums_data;
+  g_assert (state->n_checksums > 0);
+  if (!open_output_target_csum (repo, state, cancellable, error))
+    goto out;
+
+  g_variant_get (part, "(@ay ay)", &payload, &ops);
+
+  state->payload_data = g_variant_get_data (payload);
+  state->payload_size = g_variant_get_size (payload);
+
+  state->oplen = g_variant_n_children (payload);
+  state->opdata = g_variant_get_data (payload);
+  while (state->oplen > 0)
+    {
+      guint8 opcode = state->opdata[0];
+      OstreeStaticDeltaOperation *op;
+
+      if (G_UNLIKELY (opcode >= G_N_ELEMENTS (op_dispatch_table)))
+        {
+          g_set_error (error, G_IO_ERROR, G_IO_ERROR_INVALID_ARGUMENT,
+                       "Out of range opcode %u", opcode);
+          goto out;
+        }
+      op = &op_dispatch_table[opcode];
+      if (!op->func (repo, state, cancellable, error))
+        goto out;
+    }
+
+  ret = TRUE;
+ out:
+  return ret;
+}
+
+static gboolean
+dispatch_fetch (OstreeRepo    *repo,   
+                StaticDeltaExecutionState  *state,
+                GCancellable  *cancellable,  
+                GError       **error)
+{
+  g_set_error (error, G_IO_ERROR, G_IO_ERROR_NOT_SUPPORTED,
+               "Static delta fetch opcode is not implemented in this version");
+  return FALSE;
+}
+
+static guint64
+read_varuint64 (StaticDeltaExecutionState  *state)
+{
+  gsize bytes_read;
+  guint64 ret;
+  ret = _ostree_read_varuint64 (state->opdata, state->oplen, &bytes_read);
+  state->opdata += bytes_read;
+  state->oplen -= bytes_read;
+  return ret;
+}
+
+
+static gboolean
+validate_ofs (StaticDeltaExecutionState  *state,
+              guint64                     offset,
+              guint64                     length,
+              GError                    **error)
+{
+  if (G_UNLIKELY (offset + length < offset ||
+                  offset + length >= state->payload_size))
+    {
+      g_set_error (error, G_IO_ERROR, G_IO_ERROR_INVALID_ARGUMENT,
+                   "Invalid offset/length %" G_GUINT64_FORMAT "/%" G_GUINT64_FORMAT,
+                   offset, length);
+      return FALSE;
+    }
+  return TRUE;
+}
+  
+static gboolean
+dispatch_write (OstreeRepo                 *repo,
+                StaticDeltaExecutionState  *state,
+                GCancellable               *cancellable,  
+                GError                    **error)
+{
+  gboolean ret = FALSE;
+  guint64 offset;
+  guint64 length;
+  gsize bytes_written;
+
+  if (G_UNLIKELY(state->oplen < 2))
+    {
+      g_set_error (error, G_IO_ERROR, G_IO_ERROR_INVALID_ARGUMENT,
+                   "Expected at least 2 bytes for write op");
+      goto out;
+    }
+  offset = read_varuint64 (state);
+  length = read_varuint64 (state);
+  
+  if (!validate_ofs (state, offset, length, error))
+    goto out;
+
+  if (!g_output_stream_write_all (state->output_tmp_stream,
+                                  state->payload_data + offset,
+                                  length,
+                                  &bytes_written,
+                                  cancellable, error))
+    goto out;
+
+  ret = TRUE;
+ out:
+  return ret;
+}
+
+static gboolean
+dispatch_gunzip (OstreeRepo                 *repo,
+                 StaticDeltaExecutionState  *state,
+                 GCancellable               *cancellable,  
+                 GError                    **error)
+{
+  gboolean ret = FALSE;
+  guint64 offset;
+  guint64 length;
+  gs_unref_object GConverter *zlib_decomp = NULL;
+  gs_unref_object GInputStream *payload_in = NULL;
+  gs_unref_object GInputStream *zlib_in = NULL;
+
+  if (G_UNLIKELY(state->oplen < 2))
+    {
+      g_set_error (error, G_IO_ERROR, G_IO_ERROR_INVALID_ARGUMENT,
+                   "Expected at least 2 bytes for gunzip op");
+      goto out;
+    }
+  offset = read_varuint64 (state);
+  length = read_varuint64 (state);
+
+  if (!validate_ofs (state, offset, length, error))
+    goto out;
+
+  payload_in = g_memory_input_stream_new_from_data (state->payload_data + offset, length, NULL);
+  zlib_decomp = (GConverter*)g_zlib_decompressor_new (G_ZLIB_COMPRESSOR_FORMAT_RAW);
+  zlib_in = g_converter_input_stream_new (payload_in, zlib_decomp);
+
+  if (0 > g_output_stream_splice (state->output_tmp_stream, zlib_in,
+                                  G_OUTPUT_STREAM_SPLICE_CLOSE_SOURCE,
+                                  cancellable, error))
+    goto out;
+
+  ret = TRUE;
+ out:
+  return ret;
+}
+
+static gboolean
+dispatch_close (OstreeRepo                 *repo,
+                StaticDeltaExecutionState  *state,
+                GCancellable               *cancellable,  
+                GError                    **error)
+{
+  gboolean ret = FALSE;
+  char tmp_checksum[65];
+
+  if (state->checksum_index == state->n_checksums)
+    {
+      g_set_error (error, G_IO_ERROR, G_IO_ERROR_INVALID_ARGUMENT,
+                   "Too many close operations");
+      goto out;
+    }
+
+  g_assert (state->output_tmp_stream);
+  g_assert (state->output_tmp_path);
+
+  if (!g_output_stream_close (state->output_tmp_stream, cancellable, error))
+    goto out;
+
+  g_clear_object (&state->output_tmp_stream);
+
+  ostree_checksum_inplace_from_bytes (state->output_target, tmp_checksum);
+
+  if (OSTREE_OBJECT_TYPE_IS_META (state->output_objtype))
+    {
+      gs_unref_variant GVariant *metadata = NULL;
+
+      if (!ot_util_variant_map (state->output_tmp_path,
+                                ostree_metadata_variant_type (state->output_objtype),
+                                TRUE, &metadata, error))
+        goto out;
+
+      if (!ostree_repo_stage_metadata (repo, state->output_objtype, tmp_checksum,
+                                       metadata, NULL, cancellable, error))
+        goto out;
+    }
+  else
+    {
+      gs_unref_object GInputStream *in = NULL;
+      gs_unref_object GFileInfo *info = NULL;
+
+      in = (GInputStream*)g_file_read (state->output_tmp_path, cancellable, error);
+      if (!in)
+        goto out;
+
+      info = g_file_input_stream_query_info ((GFileInputStream*)in, G_FILE_ATTRIBUTE_STANDARD_SIZE,
+                                             cancellable, error);
+      if (!info)
+        goto out;
+      
+      if (!ostree_repo_stage_content (repo, tmp_checksum, in,
+                                      g_file_info_get_size (info), NULL,
+                                      cancellable, error))
+        goto out;
+    }
+
+  state->checksum_index++;
+  if (state->checksum_index < state->n_checksums)
+    {
+      if (!open_output_target_csum (repo, state, cancellable, error))
+        goto out;
+    }
+      
+  ret = TRUE;
+ out:
+  return ret;
+}
diff --git a/src/libostree/ostree-repo.c b/src/libostree/ostree-repo.c
index 713f37d..ac417de 100644
--- a/src/libostree/ostree-repo.c
+++ b/src/libostree/ostree-repo.c
@@ -94,6 +94,7 @@ ostree_repo_finalize (GObject *object)
   g_clear_object (&self->local_heads_dir);
   g_clear_object (&self->remote_heads_dir);
   g_clear_object (&self->objects_dir);
+  g_clear_object (&self->deltas_dir);
   g_clear_object (&self->uncompressed_objects_dir);
   g_clear_object (&self->remote_cache_dir);
   g_clear_object (&self->config_file);
@@ -174,6 +175,7 @@ ostree_repo_constructor (GType                  gtype,
   self->remote_heads_dir = g_file_resolve_relative_path (self->repodir, "refs/remotes");
   
   self->objects_dir = g_file_get_child (self->repodir, "objects");
+  self->deltas_dir = g_file_get_child (self->repodir, "deltas");
   self->uncompressed_objects_dir = g_file_get_child (self->repodir, "uncompressed-objects-cache");
   self->remote_cache_dir = g_file_get_child (self->repodir, "remote-cache");
   self->config_file = g_file_get_child (self->repodir, "config");
diff --git a/src/libostree/ostree-repo.h b/src/libostree/ostree-repo.h
index 73637c1..09addd6 100644
--- a/src/libostree/ostree-repo.h
+++ b/src/libostree/ostree-repo.h
@@ -376,6 +376,37 @@ gboolean ostree_repo_list_objects (OstreeRepo                  *self,
                                    GCancellable                *cancellable,
                                    GError                     **error);
 
+gboolean ostree_repo_list_static_delta_names (OstreeRepo                  *self,
+                                              GPtrArray                  **out_deltas,
+                                              GCancellable                *cancellable,
+                                              GError                     **error);
+
+/**
+ * OstreeStaticDeltaGenerateOpt:
+ * @OSTREE_STATIC_DELTA_GENERATE_OPT_LOWLATENCY: Optimize for speed of delta creation over space
+ * @OSTREE_STATIC_DELTA_GENERATE_OPT_MAJOR: Optimize for delta size (may be very slow)
+ *
+ * Parameters controlling optimization of static deltas.
+ */
+typedef enum {
+  OSTREE_STATIC_DELTA_GENERATE_OPT_LOWLATENCY,
+  OSTREE_STATIC_DELTA_GENERATE_OPT_MAJOR
+} OstreeStaticDeltaGenerateOpt;
+
+gboolean ostree_repo_static_delta_generate (OstreeRepo                   *self,
+                                            OstreeStaticDeltaGenerateOpt  opt,
+                                            const char                   *from,
+                                            const char                   *to,
+                                            GVariant                     *metadata,
+                                            GCancellable                 *cancellable,
+                                            GError                      **error);
+
+gboolean ostree_repo_static_delta_execute_offline (OstreeRepo                    *self,
+                                                   GFile                         *dir,
+                                                   gboolean                       skip_validation,
+                                                   GCancellable                  *cancellable,
+                                                   GError                      **error);
+
 GHashTable *ostree_repo_traverse_new_reachable (void);
 
 gboolean ostree_repo_traverse_dirtree (OstreeRepo         *repo,
diff --git a/src/ostree/main.c b/src/ostree/main.c
index b7d4024..7af2e03 100644
--- a/src/ostree/main.c
+++ b/src/ostree/main.c
@@ -52,6 +52,7 @@ static OstreeCommand commands[] = {
   { "remote", ostree_builtin_remote, 0 },
   { "rev-parse", ostree_builtin_rev_parse, 0 },
   { "show", ostree_builtin_show, 0 },
+  { "static-delta", ostree_builtin_static_delta, 0 },
 #ifdef HAVE_LIBSOUP 
   { "trivial-httpd", ostree_builtin_trivial_httpd, OSTREE_BUILTIN_FLAG_NO_REPO },
 #endif
diff --git a/src/ostree/ot-builtin-static-delta.c b/src/ostree/ot-builtin-static-delta.c
new file mode 100644
index 0000000..a1f11fc
--- /dev/null
+++ b/src/ostree/ot-builtin-static-delta.c
@@ -0,0 +1,123 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * Copyright (C) 2013 Colin Walters <walters verbum org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include "ot-builtins.h"
+#include "ostree.h"
+#include "otutil.h"
+
+static char *opt_from_rev;
+static char *opt_to_rev;
+static char *opt_apply;
+static int opt_depth = 1;
+
+static GOptionEntry options[] = {
+  { "from", 0, 0, G_OPTION_ARG_STRING, &opt_from_rev, "Create delta from revision REV", "REV" },
+  { "to", 0, 0, G_OPTION_ARG_STRING, &opt_to_rev, "Create delta to revision REV", "REV" },
+  { "apply", 0, 0, G_OPTION_ARG_FILENAME, &opt_apply, "Apply delta from PATH", "PATH" },
+  { NULL }
+};
+
+gboolean
+ostree_builtin_static_delta (int argc, char **argv, OstreeRepo *repo, GCancellable *cancellable, GError 
**error)
+{
+  gboolean ret = FALSE;
+  GOptionContext *context;
+  gs_unref_ptrarray GPtrArray *delta_names = NULL;
+
+  context = g_option_context_new ("Manage static delta files");
+  g_option_context_add_main_entries (context, options, NULL);
+
+  if (!g_option_context_parse (context, &argc, &argv, error))
+    goto out;
+
+  if (opt_apply)
+    {
+      gs_unref_object GFile *path = g_file_new_for_path (opt_apply);
+      if (!ostree_repo_static_delta_execute_offline (repo, path, TRUE, cancellable, error))
+        goto out;
+    }
+  else
+    {
+      if (argc >= 2 && opt_to_rev == NULL)
+        opt_to_rev = argv[1];
+
+      if (argc < 2 && opt_to_rev == NULL)
+        {
+          guint i;
+          if (!ostree_repo_list_static_delta_names (repo, &delta_names, cancellable, error))
+            goto out;
+      
+          if (delta_names->len == 0)
+            {
+              g_print ("(No static deltas)\n");
+            }
+          else
+            {
+              for (i = 0; i < delta_names->len; i++)
+                {
+                  g_print ("%s\n", (char*)delta_names->pdata[i]);
+                }
+            }
+        }
+      else if (opt_to_rev != NULL)
+        {
+          const char *from_source;
+          gs_free char *from_resolved = NULL;
+          gs_free char *to_resolved = NULL;
+          gs_free char *from_parent_str = NULL;
+
+          if (opt_from_rev == NULL)
+            {
+              from_parent_str = g_strconcat (opt_to_rev, "^", NULL);
+              from_source = from_parent_str;
+            }
+          else
+            {
+              from_source = opt_from_rev;
+            }
+
+          if (!ostree_repo_resolve_rev (repo, from_source, FALSE, &from_resolved, error))
+            goto out;
+          if (!ostree_repo_resolve_rev (repo, opt_to_rev, FALSE, &to_resolved, error))
+            goto out;
+
+          g_print ("Generating static delta:\n");
+          g_print ("  From: %s\n", from_resolved);
+          g_print ("  To:   %s\n", to_resolved);
+          if (!ostree_repo_static_delta_generate (repo, OSTREE_STATIC_DELTA_GENERATE_OPT_MAJOR,
+                                                  from_resolved, to_resolved, NULL,
+                                                  cancellable, error))
+            goto out;
+        }
+      else
+        {
+          ot_util_usage_error (context, "--from=REV must be specified", error);
+          goto out;
+        }
+    }
+
+  ret = TRUE;
+ out:
+  if (context)
+    g_option_context_free (context);
+  return ret;
+}
diff --git a/src/ostree/ot-builtins.h b/src/ostree/ot-builtins.h
index cbd7847..fee66f2 100644
--- a/src/ostree/ot-builtins.h
+++ b/src/ostree/ot-builtins.h
@@ -45,6 +45,7 @@ BUILTINPROTO(refs);
 BUILTINPROTO(reset);
 BUILTINPROTO(fsck);
 BUILTINPROTO(show);
+BUILTINPROTO(static_delta);
 BUILTINPROTO(rev_parse);
 BUILTINPROTO(remote);
 BUILTINPROTO(write_refs);
diff --git a/tests/test-delta.sh b/tests/test-delta.sh
new file mode 100755
index 0000000..3c160fa
--- /dev/null
+++ b/tests/test-delta.sh
@@ -0,0 +1,70 @@
+#!/bin/bash
+#
+# Copyright (C) 2011,2013 Colin Walters <walters verbum org>
+#
+# This library is free software; you can redistribute it and/or
+# modify it under the terms of the GNU Lesser General Public
+# License as published by the Free Software Foundation; either
+# version 2 of the License, or (at your option) any later version.
+#
+# This library is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+# Lesser General Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with this library; if not, write to the
+# Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+# Boston, MA 02111-1307, USA.
+
+set -e
+
+. $(dirname $0)/libtest.sh
+
+bindatafiles="bash true ostree"
+morebindatafiles="false ls"
+
+echo '1..2'
+
+mkdir repo
+ostree --repo=repo init --mode=archive-z2
+
+mkdir files
+for bin in ${bindatafiles}; do
+    cp $(which ${bin}) files
+done
+
+ostree --repo=repo commit -b test -s test --tree=dir=files
+
+function permuteFile() {
+    permutation=$(($1 % 2))
+    output=$2
+    case $permutation in
+       0) dd if=/dev/zero count=40 bs=1 >> $output;;
+       1) echo aheader | cat - $output >> $output.new && mv $output.new $output;;
+    esac
+}
+
+function permuteDirectory() {
+    permutation=$1
+    dir=$2
+    for x in ${dir}/*; do
+       for z in $(seq ${permutation}); do
+           permuteFile ${z} ${x}
+       done
+    done
+}
+
+permuteDirectory 1 files
+ostree --repo=repo commit -b test -s test --tree=dir=files
+
+origrev=$(ostree --repo=repo rev-parse test^)
+newrev=$(ostree --repo=repo rev-parse test)
+ostree static-delta --repo=repo --tune=continuous --from-ref=test
+
+assert_has_file repo/deltas/${origrev}-${newrev}
+
+
+
+
+


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]