path: root/src/libostree/ostree-repo-static-delta-compilation-analysis.c

/*
 * Copyright (C) 2015 Colin Walters <walters@verbum.org>
 *
 * SPDX-License-Identifier: LGPL-2.0+
 *
 * 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, see <https://www.gnu.org/licenses/>.
 */

#include "config.h"

#include <string.h>
#include <gio/gunixoutputstream.h>

#include "ostree-core-private.h"
#include "ostree-repo-private.h"
#include "ostree-lzma-compressor.h"
#include "ostree-repo-static-delta-private.h"
#include "ostree-diff.h"
#include "ostree-rollsum.h"
#include "otutil.h"
#include "ostree-varint.h"

void
_ostree_delta_content_sizenames_free (gpointer v)
{
  OstreeDeltaContentSizeNames *ce = v;
  g_free (ce->checksum);
  g_ptr_array_unref (ce->basenames);
  g_free (ce);
}

static gboolean
build_content_sizenames_recurse (OstreeRepo                     *repo,
                                 OstreeRepoCommitTraverseIter   *iter,
                                 GHashTable                     *sizenames_map,
                                 GHashTable                     *include_only_objects,
                                 GCancellable                   *cancellable,
                                 GError                        **error)
{
  gboolean ret = FALSE;

  while (TRUE)
    {
      OstreeRepoCommitIterResult iterres =
        ostree_repo_commit_traverse_iter_next (iter, cancellable, error);
          
      if (iterres == OSTREE_REPO_COMMIT_ITER_RESULT_ERROR)
        goto out;
      else if (iterres == OSTREE_REPO_COMMIT_ITER_RESULT_END)
        break;
      else if (iterres == OSTREE_REPO_COMMIT_ITER_RESULT_FILE)
        {
          char *name;
          char *checksum;
          OstreeDeltaContentSizeNames *csizenames;
            
          ostree_repo_commit_traverse_iter_get_file (iter, &name, &checksum);

          if (include_only_objects && !g_hash_table_contains (include_only_objects, checksum))
            continue;

          csizenames = g_hash_table_lookup (sizenames_map, checksum);
          if (!csizenames)
            {
              g_autoptr(GFileInfo) finfo = NULL;

              if (!ostree_repo_load_file (repo, checksum,
                                          NULL, &finfo, NULL,
                                          cancellable, error))
                goto out;

              if (g_file_info_get_file_type (finfo) != G_FILE_TYPE_REGULAR)
                continue;

              csizenames = g_new0 (OstreeDeltaContentSizeNames, 1);
              csizenames->checksum = g_strdup (checksum);
              csizenames->size = g_file_info_get_size (finfo);
              g_hash_table_replace (sizenames_map, csizenames->checksum, csizenames);
            }

          if (!csizenames->basenames)
            csizenames->basenames = g_ptr_array_new_with_free_func (g_free);
          g_ptr_array_add (csizenames->basenames, g_strdup (name));
        }
      else if (iterres == OSTREE_REPO_COMMIT_ITER_RESULT_DIR)
        {
          char *name;
          char *content_checksum;
          char *meta_checksum;
          g_autoptr(GVariant) dirtree = NULL;
          ostree_cleanup_repo_commit_traverse_iter
            OstreeRepoCommitTraverseIter subiter = { 0, };

          ostree_repo_commit_traverse_iter_get_dir (iter, &name, &content_checksum, &meta_checksum);
          
          if (!ostree_repo_load_variant (repo, OSTREE_OBJECT_TYPE_DIR_TREE,
                                         content_checksum, &dirtree,
                                         error))
            goto out;

          if (!ostree_repo_commit_traverse_iter_init_dirtree (&subiter, repo, dirtree,
                                                              OSTREE_REPO_COMMIT_TRAVERSE_FLAG_NONE,
                                                              error))
            goto out;

          if (!build_content_sizenames_recurse (repo, &subiter,
                                                sizenames_map, include_only_objects,
                                                cancellable, error))
            goto out;
        }
      else
        g_assert_not_reached ();
    }
  ret = TRUE;
 out:
  return ret;
}

static int
compare_sizenames (const void  *a,
                   const void  *b)
{
  OstreeDeltaContentSizeNames *sn_a = *(OstreeDeltaContentSizeNames**)(void*)a;
  OstreeDeltaContentSizeNames *sn_b = *(OstreeDeltaContentSizeNames**)(void*)b;

  return sn_a->size - sn_b->size;
}

/*
 * Generate a sorted array of [(checksum: str, size: uint64, names: array[string]), ...]
 * for regular file content.
 */
static gboolean
build_content_sizenames_filtered (OstreeRepo              *repo,
                                  GVariant                *commit,
                                  GHashTable              *include_only_objects,
                                  GPtrArray              **out_sizenames,
                                  GCancellable            *cancellable,
                                  GError                 **error)
{
  gboolean ret = FALSE;
  g_autoptr(GPtrArray) ret_sizenames =
    g_ptr_array_new_with_free_func (_ostree_delta_content_sizenames_free);
  g_autoptr(GHashTable) sizenames_map =
    g_hash_table_new_full (g_str_hash, g_str_equal, NULL, _ostree_delta_content_sizenames_free);
  ostree_cleanup_repo_commit_traverse_iter
    OstreeRepoCommitTraverseIter iter = { 0, };

  if (!ostree_repo_commit_traverse_iter_init_commit (&iter, repo, commit,
                                                     OSTREE_REPO_COMMIT_TRAVERSE_FLAG_NONE,
                                                     error))
    goto out;

  if (!build_content_sizenames_recurse (repo, &iter, sizenames_map, include_only_objects,
                                        cancellable, error))
    goto out;

  { GHashTableIter hashiter;
    gpointer hkey, hvalue;

    g_hash_table_iter_init (&hashiter, sizenames_map);
    while (g_hash_table_iter_next (&hashiter, &hkey, &hvalue))
      {
        g_hash_table_iter_steal (&hashiter);
        g_ptr_array_add (ret_sizenames, hvalue);
      }
  }

  g_ptr_array_sort (ret_sizenames, compare_sizenames);

  ret = TRUE;
  if (out_sizenames)
    *out_sizenames = g_steal_pointer (&ret_sizenames);
 out:
  return ret;
}

static gboolean
string_array_nonempty_intersection (GPtrArray    *a,
                                    GPtrArray    *b,
                                    gboolean      fuzzy)
{
  guint i;
  for (i = 0; i < a->len; i++)
    {
      guint j;
      const char *a_str = a->pdata[i];
      const char *a_dot = strchr (a_str, '.');
      for (j = 0; j < b->len; j++)
        {
          const char *b_str = b->pdata[j];
          const char *b_dot = strchr (b_str, '.');
          /* When doing fuzzy comparison, just compare the part before the '.' if it exists.  */
          if (fuzzy && a_dot && b_dot && b_dot - b_str && b_dot - b_str == a_dot - a_str)
            {
              if (strncmp (a_str, b_str, a_dot - a_str) == 0)
                return TRUE;
            }
          else
            {
              if (strcmp (a_str, b_str) == 0)
                return TRUE;
            }
        }
    }
  return FALSE;
}

static gboolean
sizename_is_delta_candidate (OstreeDeltaContentSizeNames *sizename)
{
  /* Don't build candidates for the empty object */
  if (sizename->size == 0)
    return FALSE;

  /* Look for known non-delta-able files (currently just compression like xz) */
  for (guint i = 0; i < sizename->basenames->len; i++)
    {
      const char *name = sizename->basenames->pdata[i];
      /* We could replace this down the line with g_content_type_guess() or so,
       * but it's not clear to me that's a major win; we'd still need to
       * maintain a list of compression formats, and this doesn't require
       * allocation.
       * NB: We explicitly don't have .gz here in case someone might be
       * using --rsyncable for that.
       */
      const char *dot = strrchr (name, '.');
      if (!dot)
        continue;
      const char *extension = dot+1;
      /* Don't add .gz here, see above */
      if (g_str_equal (extension, "xz") || g_str_equal (extension, "bz2"))
        return FALSE;
    }

  /* Let's try it */
  return TRUE;
}

/*
 * Build up a map of files with matching basenames and similar size,
 * and use it to find apparently similar objects.
 *
 * @new_reachable_regfile_content is a Set<checksum> of new regular
 * file objects.
 *
 * Currently, @out_modified_regfile_content will be a Map<to checksum,from checksum>;
 * however in the future it would be easy to have this function return
 * multiple candidate matches.  The hard part would be changing
 * the delta compiler to iterate over all matches, determine
 * a cost for each one, then pick the best.
 */
gboolean
_ostree_delta_compute_similar_objects (OstreeRepo                 *repo,
                                       GVariant                   *from_commit,
                                       GVariant                   *to_commit,
                                       GHashTable                 *new_reachable_regfile_content,
                                       guint                       similarity_percent_threshold,
                                       GHashTable                **out_modified_regfile_content,
                                       GCancellable               *cancellable,
                                       GError                    **error)
{
  gboolean ret = FALSE;
  g_autoptr(GHashTable) ret_modified_regfile_content =
    g_hash_table_new_full (g_str_hash, g_str_equal, g_free, g_free);
  g_autoptr(GPtrArray) from_sizes = NULL;
  g_autoptr(GPtrArray) to_sizes = NULL;
  guint i, j;
  guint lower;
  guint upper;

  if (!build_content_sizenames_filtered (repo, from_commit, NULL,
                                         &from_sizes,
                                         cancellable, error))
    goto out;

  if (!build_content_sizenames_filtered (repo, to_commit, new_reachable_regfile_content,
                                         &to_sizes,
                                         cancellable, error))
    goto out;

  /* Iterate over all newly added objects, find objects which have
   * similar basename and sizes.
   *
   * Because the arrays are sorted by size, we can maintain a `lower`
   * bound on the original (from) objects to start searching.
   */
  lower = 0;
  upper = from_sizes->len;
  for (i = 0; i < to_sizes->len; i++)
    {
      int fuzzy;
      gboolean found = FALSE;
      OstreeDeltaContentSizeNames *to_sizenames = to_sizes->pdata[i];
      const guint64 min_threshold = to_sizenames->size *
        (1.0-similarity_percent_threshold/100.0);
      const guint64 max_threshold = to_sizenames->size *
        (1.0+similarity_percent_threshold/100.0);

      if (!sizename_is_delta_candidate (to_sizenames))
        continue;

      for (fuzzy = 0; fuzzy < 2 && !found; fuzzy++)
        {
          for (j = lower; j < upper; j++)
            {
              OstreeDeltaContentSizeNames *from_sizenames = from_sizes->pdata[j];
              if (!sizename_is_delta_candidate (from_sizenames))
                continue;

              if (from_sizenames->size < min_threshold)
                {
                  lower++;
                  continue;
                }

              if (from_sizenames->size > max_threshold)
                break;

              if (!string_array_nonempty_intersection (from_sizenames->basenames,
                                                       to_sizenames->basenames,
                                                       fuzzy == 1))
                {
                  continue;
                }

              /* Only one candidate right now */
              g_hash_table_insert (ret_modified_regfile_content,
                                   g_strdup (to_sizenames->checksum),
                                   g_strdup (from_sizenames->checksum));
              found = TRUE;
              break;
            }
        }
    }

  ret = TRUE;
  if (out_modified_regfile_content)
    *out_modified_regfile_content = g_steal_pointer (&ret_modified_regfile_content);
 out:
  return ret;
}