/src/git/pack-bitmap-write.c

Source
#define DISABLE_SIGN_COMPARE_WARNINGS

#include "git-compat-util.h"
#include "environment.h"
#include "gettext.h"
#include "hex.h"
#include "odb.h"
#include "commit.h"
#include "diff.h"
#include "revision.h"
#include "progress.h"
#include "pack.h"
#include "pack-bitmap.h"
#include "hash-lookup.h"
#include "pack-objects.h"
#include "path.h"
#include "commit-reach.h"
#include "prio-queue.h"
#include "trace2.h"
#include "tree.h"
#include "tree-walk.h"
#include "pseudo-merge.h"
#include "oid-array.h"
#include "config.h"
#include "alloc.h"
#include "refs.h"
#include "strmap.h"
#include "midx.h"
#include "pack-revindex.h"

struct bitmapped_commit {
  struct commit *commit;
  struct ewah_bitmap *bitmap;
  struct ewah_bitmap *write_as;
  struct ewah_bitmap *pseudo_merge_parents;
  int flags;
  int xor_offset;
  uint32_t commit_pos;
  unsigned pseudo_merge : 1;
};

static inline int bitmap_writer_nr_selected_commits(struct bitmap_writer *writer)
{
  return writer->selected_nr - writer->pseudo_merges_nr;
}

void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r,
      struct packing_data *pdata,
      struct multi_pack_index *midx)
{
  memset(writer, 0, sizeof(struct bitmap_writer));
  if (writer->bitmaps)
    BUG("bitmap writer already initialized");
  writer->repo = r;
  writer->bitmaps = kh_init_oid_map();
  writer->pseudo_merge_commits = kh_init_oid_map();
  writer->to_pack = pdata;
  writer->midx = midx;

  string_list_init_dup(&writer->pseudo_merge_groups);

  load_pseudo_merges_from_config(r, &writer->pseudo_merge_groups);
}

static void free_pseudo_merge_commit_idx(struct pseudo_merge_commit_idx *idx)
{
  if (!idx)
    return;
  free(idx->pseudo_merge);
  free(idx);
}

static void pseudo_merge_group_release_cb(void *payload, const char *name UNUSED)
{
  pseudo_merge_group_release(payload);
  free(payload);
}

void bitmap_writer_free(struct bitmap_writer *writer)
{
  uint32_t i;
  struct pseudo_merge_commit_idx *idx;

  if (!writer)
    return;

  ewah_free(writer->commits);
  ewah_free(writer->trees);
  ewah_free(writer->blobs);
  ewah_free(writer->tags);

  kh_destroy_oid_map(writer->bitmaps);
  free(writer->pos_cache);

  kh_foreach_value(writer->pseudo_merge_commits, idx,
       free_pseudo_merge_commit_idx(idx));
  kh_destroy_oid_map(writer->pseudo_merge_commits);
  string_list_clear_func(&writer->pseudo_merge_groups,
             pseudo_merge_group_release_cb);

  for (i = 0; i < writer->selected_nr; i++) {
    struct bitmapped_commit *bc = &writer->selected[i];
    if (bc->write_as != bc->bitmap)
      ewah_free(bc->write_as);
    ewah_free(bc->bitmap);
    ewah_free(bc->pseudo_merge_parents);
  }
  free(writer->selected);
}

void bitmap_writer_show_progress(struct bitmap_writer *writer, int show)
{
  writer->show_progress = show;
}

/**
 * Build the initial type index for the packfile or multi-pack-index
 */
void bitmap_writer_build_type_index(struct bitmap_writer *writer,
            struct pack_idx_entry **index)
{
  uint32_t i;
  uint32_t base_objects = 0;

  if (writer->midx)
    base_objects = writer->midx->num_objects +
      writer->midx->num_objects_in_base;

  writer->commits = ewah_new();
  writer->trees = ewah_new();
  writer->blobs = ewah_new();
  writer->tags = ewah_new();
  ALLOC_ARRAY(writer->to_pack->in_pack_pos, writer->to_pack->nr_objects);

  for (i = 0; i < writer->to_pack->nr_objects; ++i) {
    struct object_entry *entry = (struct object_entry *)index[i];
    enum object_type real_type;

    oe_set_in_pack_pos(writer->to_pack, entry, i);

    switch (oe_type(entry)) {
    case OBJ_COMMIT:
    case OBJ_TREE:
    case OBJ_BLOB:
    case OBJ_TAG:
      real_type = oe_type(entry);
      break;

    default:
      real_type = odb_read_object_info(writer->to_pack->repo->objects,
               &entry->idx.oid, NULL);
      break;
    }

    switch (real_type) {
    case OBJ_COMMIT:
      ewah_set(writer->commits, i + base_objects);
      break;

    case OBJ_TREE:
      ewah_set(writer->trees, i + base_objects);
      break;

    case OBJ_BLOB:
      ewah_set(writer->blobs, i + base_objects);
      break;

    case OBJ_TAG:
      ewah_set(writer->tags, i + base_objects);
      break;

    default:
      die("Missing type information for %s (%d/%d)",
          oid_to_hex(&entry->idx.oid), real_type,
          oe_type(entry));
    }
  }
}

int bitmap_writer_has_bitmapped_object_id(struct bitmap_writer *writer,
            const struct object_id *oid)
{
  return kh_get_oid_map(writer->bitmaps, *oid) != kh_end(writer->bitmaps);
}

/**
 * Compute the actual bitmaps
 */

void bitmap_writer_push_commit(struct bitmap_writer *writer,
             struct commit *commit, unsigned pseudo_merge)
{
  if (writer->selected_nr >= writer->selected_alloc) {
    writer->selected_alloc = (writer->selected_alloc + 32) * 2;
    REALLOC_ARRAY(writer->selected, writer->selected_alloc);
  }

  if (!pseudo_merge) {
    int hash_ret;
    khiter_t hash_pos = kh_put_oid_map(writer->bitmaps,
               commit->object.oid,
               &hash_ret);

    if (!hash_ret)
      die(_("duplicate entry when writing bitmap index: %s"),
          oid_to_hex(&commit->object.oid));
    kh_value(writer->bitmaps, hash_pos) = NULL;
  }

  writer->selected[writer->selected_nr].commit = commit;
  writer->selected[writer->selected_nr].bitmap = NULL;
  writer->selected[writer->selected_nr].write_as = NULL;
  writer->selected[writer->selected_nr].flags = 0;
  writer->selected[writer->selected_nr].pseudo_merge = pseudo_merge;
  writer->selected[writer->selected_nr].pseudo_merge_parents = NULL;

  writer->selected_nr++;
}

struct bitmap_pos_cache_entry {
  struct object_id oid;
  uint32_t pos;
};

#define BITMAP_POS_MIN_CACHE_SIZE (1U << 10)
#define BITMAP_POS_MAX_CACHE_SIZE (1U << 21)
#define BITMAP_POS_CACHE_VALID    (1U << 31)

static void bitmap_writer_init_pos_cache(struct bitmap_writer *writer)
{
  if (writer->pos_cache)
    return;

  writer->pos_cache_nr = BITMAP_POS_MIN_CACHE_SIZE;

  while (writer->pos_cache_nr < writer->to_pack->nr_objects &&
         writer->pos_cache_nr < BITMAP_POS_MAX_CACHE_SIZE)
    writer->pos_cache_nr <<= 1;

  CALLOC_ARRAY(writer->pos_cache, writer->pos_cache_nr);
}

static size_t bitmap_writer_pos_cache_slot(struct bitmap_writer *writer,
             const struct object_id *oid)
{
  return oidhash(oid) & (writer->pos_cache_nr - 1);
}

static bool bitmap_writer_pos_cache_valid(struct bitmap_writer *writer,
            size_t slot)
{
  return !!(writer->pos_cache[slot].pos & BITMAP_POS_CACHE_VALID);
}

static int find_cached_object_pos(struct bitmap_writer *writer,
          const struct object_id *oid, uint32_t *pos)
{
  size_t slot = bitmap_writer_pos_cache_slot(writer, oid);

  if (bitmap_writer_pos_cache_valid(writer, slot) &&
      oideq(&writer->pos_cache[slot].oid, oid)) {
    writer->pos_cache_hits++;
    *pos = writer->pos_cache[slot].pos & ~BITMAP_POS_CACHE_VALID;
    return 1;
  }

  writer->pos_cache_misses++;
  return 0;
}

static uint32_t store_cached_object_pos(struct bitmap_writer *writer,
          const struct object_id *oid,
          uint32_t pos)
{
  size_t slot;

  if (pos & BITMAP_POS_CACHE_VALID)
    return pos; /* too large to cache */

  slot = bitmap_writer_pos_cache_slot(writer, oid);

  oidcpy(&writer->pos_cache[slot].oid, oid);
  writer->pos_cache[slot].pos = pos | BITMAP_POS_CACHE_VALID;

  return pos;
}

static uint32_t find_object_pos(struct bitmap_writer *writer,
        const struct object_id *oid, int *found)
{
  struct object_entry *entry;
  uint32_t pos;

  bitmap_writer_init_pos_cache(writer);

  if (find_cached_object_pos(writer, oid, &pos)) {
    if (found)
      *found = 1;
    return pos;
  }

  entry = packlist_find(writer->to_pack, oid);
  if (entry) {
    uint32_t base_objects = 0;

    if (writer->midx)
      base_objects = writer->midx->num_objects +
        writer->midx->num_objects_in_base;
    pos = oe_in_pack_pos(writer->to_pack, entry) + base_objects;
  } else if (writer->midx) {
    uint32_t at;

    if (!bsearch_midx(oid, writer->midx, &at))
      goto missing;
    if (midx_to_pack_pos(writer->midx, at, &pos) < 0)
      goto missing;
  } else {
    goto missing;
  }

  if (found)
    *found = 1;
  return store_cached_object_pos(writer, oid, pos);

missing:
  if (found)
    *found = 0;
  warning("Failed to write bitmap index. Packfile doesn't have full closure "
    "(object %s is missing)", oid_to_hex(oid));
  return 0;
}

static int bitmapped_commit_date_cmp(const void *_a, const void *_b)
{
  const struct bitmapped_commit *a = _a;
  const struct bitmapped_commit *b = _b;

  if (a->commit->date < b->commit->date)
    return -1;
  if (a->commit->date > b->commit->date)
    return 1;
  return 0;
}

static void compute_xor_offsets(struct bitmap_writer *writer)
{
  static const int MAX_XOR_OFFSET_SEARCH = 10;

  int i, next = 0;
  int nr = bitmap_writer_nr_selected_commits(writer);

  if (nr > 1) {
    QSORT(writer->selected, nr, bitmapped_commit_date_cmp);

    for (i = 0; i < nr; i++) {
      struct bitmapped_commit *stored = &writer->selected[i];
      khiter_t hash_pos = kh_get_oid_map(writer->bitmaps,
                 stored->commit->object.oid);

      if (hash_pos == kh_end(writer->bitmaps))
        BUG("selected commit missing from bitmap map: %s",
            oid_to_hex(&stored->commit->object.oid));

      kh_value(writer->bitmaps, hash_pos) = stored;
    }
  }

  while (next < writer->selected_nr) {
    struct bitmapped_commit *stored = &writer->selected[next];
    int best_offset = 0;
    struct ewah_bitmap *best_bitmap = stored->bitmap;
    struct ewah_bitmap *test_xor;

    if (stored->pseudo_merge)
      goto next;

    for (i = 1; i <= MAX_XOR_OFFSET_SEARCH; ++i) {
      int curr = next - i;

      if (curr < 0)
        break;
      if (writer->selected[curr].pseudo_merge)
        continue;

      test_xor = ewah_pool_new();
      ewah_xor(writer->selected[curr].bitmap, stored->bitmap, test_xor);

      if (test_xor->buffer_size < best_bitmap->buffer_size) {
        if (best_bitmap != stored->bitmap)
          ewah_pool_free(best_bitmap);

        best_bitmap = test_xor;
        best_offset = i;
      } else {
        ewah_pool_free(test_xor);
      }
    }

next:
    stored->xor_offset = best_offset;
    stored->write_as = best_bitmap;

    next++;
  }
}

struct bb_commit {
  struct commit_list *reverse_edges;
  struct bitmap *commit_mask;
  struct bitmap *bitmap;
  unsigned selected:1,
     maximal:1,
     pseudo_merge:1;
  unsigned idx; /* within selected array */
};

static void clear_bb_commit(struct bb_commit *commit)
{
  commit_list_free(commit->reverse_edges);
  bitmap_free(commit->commit_mask);
  bitmap_free(commit->bitmap);
}

define_commit_slab(bb_data, struct bb_commit);

struct bitmap_builder {
  struct bb_data data;
  struct commit_stack commits;
};

static void bitmap_builder_init(struct bitmap_builder *bb,
        struct bitmap_writer *writer,
        struct bitmap_index *old_bitmap)
{
  struct rev_info revs;
  struct commit *commit;
  struct commit_list *reusable = NULL;
  struct commit_list *r;
  unsigned int i, num_maximal = 0;

  init_bb_data(&bb->data);
  commit_stack_init(&bb->commits);

  reset_revision_walk();
  repo_init_revisions(writer->to_pack->repo, &revs, NULL);
  revs.topo_order = 1;
  revs.first_parent_only = 1;

  for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) {
    struct bitmapped_commit *bc = &writer->selected[i];
    struct bb_commit *ent = bb_data_at(&bb->data, bc->commit);

    if (bc->pseudo_merge)
      BUG("unexpected pseudo-merge at %"PRIuMAX,
          (uintmax_t)i);

    ent->selected = 1;
    ent->maximal = 1;
    ent->pseudo_merge = 0;
    ent->idx = i;

    ent->commit_mask = bitmap_new();
    bitmap_set(ent->commit_mask, i);

    add_pending_object(&revs, &bc->commit->object, "");
  }

  if (prepare_revision_walk(&revs))
    die("revision walk setup failed");

  while ((commit = get_revision(&revs))) {
    struct commit_list *p = commit->parents;
    struct bb_commit *c_ent;

    parse_commit_or_die(commit);

    c_ent = bb_data_at(&bb->data, commit);

    /*
     * If there is no commit_mask, there is no reason to iterate
     * over this commit; it is not selected (if it were, it would
     * not have a blank commit mask) and all its children have
     * existing bitmaps (see the comment starting with "This commit
     * has an existing bitmap" below), so it does not contribute
     * anything to the final bitmap file or its descendants.
     */
    if (!c_ent->commit_mask)
      continue;

    if (old_bitmap && bitmap_for_commit(old_bitmap, commit)) {
      /*
       * This commit has an existing bitmap, so we can
       * get its bits immediately without an object
       * walk. That is, it is reusable as-is and there is no
       * need to continue walking beyond it.
       *
       * Mark it as such and add it to bb->commits separately
       * to avoid allocating a position in the commit mask.
       */
      commit_list_insert(commit, &reusable);
      goto next;
    }

    if (c_ent->maximal) {
      num_maximal++;
      commit_stack_push(&bb->commits, commit);
    }

    if (p) {
      struct bb_commit *p_ent = bb_data_at(&bb->data, p->item);
      int c_not_p, p_not_c;

      if (!p_ent->commit_mask) {
        p_ent->commit_mask = bitmap_new();
        c_not_p = 1;
        p_not_c = 0;
      } else {
        c_not_p = bitmap_is_subset(c_ent->commit_mask, p_ent->commit_mask);
        p_not_c = bitmap_is_subset(p_ent->commit_mask, c_ent->commit_mask);
      }

      if (!c_not_p)
        continue;

      bitmap_or(p_ent->commit_mask, c_ent->commit_mask);

      if (p_not_c)
        p_ent->maximal = 1;
      else {
        p_ent->maximal = 0;
        commit_list_free(p_ent->reverse_edges);
        p_ent->reverse_edges = NULL;
      }

      if (c_ent->maximal) {
        commit_list_insert(commit, &p_ent->reverse_edges);
      } else {
        struct commit_list *cc = c_ent->reverse_edges;

        for (; cc; cc = cc->next) {
          if (!commit_list_contains(cc->item, p_ent->reverse_edges))
            commit_list_insert(cc->item, &p_ent->reverse_edges);
        }
      }
    }

next:
    bitmap_free(c_ent->commit_mask);
    c_ent->commit_mask = NULL;
  }

  for (r = reusable; r; r = r->next) {
    commit_stack_push(&bb->commits, r->item);
  }

  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "num_selected_commits", writer->selected_nr);
  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "num_maximal_commits", num_maximal);

  release_revisions(&revs);
  commit_list_free(reusable);
}

static void bitmap_builder_clear(struct bitmap_builder *bb)
{
  deep_clear_bb_data(&bb->data, clear_bb_commit);
  commit_stack_clear(&bb->commits);
}

static int fill_bitmap_tree(struct bitmap_writer *writer,
          struct bitmap *bitmap,
          struct tree *tree,
          uint32_t pos)
{
  int found;
  struct tree_desc desc;
  struct name_entry entry;

  bitmap_set(bitmap, pos);

  if (repo_parse_tree(writer->repo, tree) < 0)
    die("unable to load tree object %s",
        oid_to_hex(&tree->object.oid));
  init_tree_desc(&desc, &tree->object.oid, tree->buffer, tree->size);

  while (tree_entry(&desc, &entry)) {
    switch (object_type(entry.mode)) {
    case OBJ_TREE:
      pos = find_object_pos(writer, &entry.oid, &found);
      if (!found)
        return -1;
      if (bitmap_get(bitmap, pos)) {
        /*
         * If our bit is already set, then there
         * is nothing to do. Both this tree and
         * all of its children will be set.
         */
        break;
      }

      if (fill_bitmap_tree(writer, bitmap,
               lookup_tree(writer->repo,
               &entry.oid), pos) < 0)
        return -1;
      break;
    case OBJ_BLOB:
      pos = find_object_pos(writer, &entry.oid, &found);
      if (!found)
        return -1;
      bitmap_set(bitmap, pos);
      break;
    default:
      /* Gitlink, etc; not reachable */
      break;
    }
  }

  free_tree_buffer(tree);
  return 0;
}

static int reused_bitmaps_nr;
static int reused_pseudo_merge_bitmaps_nr;
static int pseudo_merge_bitmap_nr;
static int pseudo_merge_bitmap_parents;

static int fill_bitmap_commit_calls_nr;
static int fill_bitmap_commit_found_ancestor_nr;

static int fill_bitmap_commit(struct bitmap_writer *writer,
            struct bb_commit *ent,
            struct commit *commit,
            struct prio_queue *queue,
            struct prio_queue *tree_queue,
            struct bitmap_index *old_bitmap,
            const uint32_t *mapping)
{
  struct commit *c;
  struct tree *t;
  int found;
  int from_pseudo_merge = commit->object.flags & BITMAP_PSEUDO_MERGE;
  uint32_t pos;

  if (ent->pseudo_merge)
    BUG("unexpected pseudo-merge commit in fill_bitmap_commit()");

  fill_bitmap_commit_calls_nr++;

  if (!ent->bitmap)
    ent->bitmap = bitmap_new();

  prio_queue_put(queue, commit);

  while ((c = prio_queue_get(queue))) {
    struct commit_list *p;

    if (old_bitmap && mapping) {
      struct ewah_bitmap *old;
      struct bitmap *remapped = bitmap_new();

      old = bitmap_for_commit(old_bitmap, c);
      /*
       * If this commit has an old bitmap, then translate that
       * bitmap and add its bits to this one. No need to walk
       * parents or the tree for this commit.
       */
      if (old && !rebuild_bitmap(mapping, old, remapped)) {
        bitmap_or(ent->bitmap, remapped);
        bitmap_free(remapped);
        reused_bitmaps_nr++;
        continue;
      }
      bitmap_free(remapped);
    }

    /*
     * If we encounter an ancestor for which we have already
     * computed a bitmap during this build (i.e. a regular
     * selected commit processed earlier in topo order), we can
     * short-circuit the walk: its stored bitmap already covers
     * the commit itself, its tree, and all of its ancestors.
     */
    if (c != commit) {
      khiter_t hash_pos = kh_get_oid_map(writer->bitmaps,
                 c->object.oid);
      if (hash_pos != kh_end(writer->bitmaps)) {
        struct bitmapped_commit *stored =
          kh_value(writer->bitmaps, hash_pos);
        if (stored && stored->bitmap) {
          fill_bitmap_commit_found_ancestor_nr++;
          bitmap_or_ewah(ent->bitmap,
                   stored->bitmap);
          continue;
        }
      }
    }

    /*
     * Mark ourselves and queue our tree. The commit
     * walk ensures we cover all parents.
     */
    if (!(c->object.flags & BITMAP_PSEUDO_MERGE)) {
      struct tree *tree;

      if (from_pseudo_merge && !c->object.parsed) {
        /*
         * Commits reachable from selected
         * non-pseudo-merges are already parsed
         * by the regular bitmap build.
         *
         * However, pseudo-merge fills can also
         * reach commits that were not covered
         * there, so parse any such leftovers
         * before reading their tree or parents.
         */
        if (repo_parse_commit(writer->repo, c))
          return -1;
      }

      pos = find_object_pos(writer, &c->object.oid, &found);
      if (!found)
        return -1;
      bitmap_set(ent->bitmap, pos);

      tree = repo_get_commit_tree(writer->repo, c);
      if (!tree)
        return -1;
      prio_queue_put(tree_queue, tree);
    }

    for (p = c->parents; p; p = p->next) {
      pos = find_object_pos(writer, &p->item->object.oid,
                &found);
      if (!found)
        return -1;
      if (!bitmap_get(ent->bitmap, pos)) {
        bitmap_set(ent->bitmap, pos);
        prio_queue_put(queue, p->item);
      }
    }
  }

  while ((t = prio_queue_get(tree_queue))) {
    int found;

    pos = find_object_pos(writer, &t->object.oid, &found);
    if (!found)
      return -1;
    if (bitmap_get(ent->bitmap, pos)) {
      /*
       * If our bit is already set, then there is
       * nothing to do. Both this tree and all of its
       * children will be set.
       */
      continue;
    }

    if (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0)
      return -1;
  }
  return 0;
}

static int reuse_pseudo_merge_bitmap(struct bitmap_index *old_bitmap,
             const uint32_t *mapping,
             struct commit *merge,
             struct ewah_bitmap **out)
{
  struct ewah_bitmap *old;
  struct bitmap *remapped;

  if (!old_bitmap || !mapping)
    return 0;

  old = pseudo_merge_bitmap_for_commit(old_bitmap, merge);
  if (!old)
    return 0;

  remapped = bitmap_new();
  if (rebuild_bitmap(mapping, old, remapped) < 0) {
    bitmap_free(remapped);
    return 0;
  }

  *out = bitmap_to_ewah(remapped);
  bitmap_free(remapped);
  reused_pseudo_merge_bitmaps_nr++;
  return 1;
}

static int build_pseudo_merge_bitmap(struct bitmap_writer *writer,
             struct bitmap_index *old_bitmap,
             const uint32_t *mapping,
             struct commit *merge,
             struct ewah_bitmap **out)
{
  struct bb_commit ent = { 0 };
  struct prio_queue queue = { NULL };
  struct prio_queue tree_queue = { NULL };
  unsigned parents = commit_list_count(merge->parents);
  int ret;

  ent.bitmap = bitmap_new();

  pseudo_merge_bitmap_nr++;
  pseudo_merge_bitmap_parents += parents;

  if (reuse_pseudo_merge_bitmap(old_bitmap, mapping, merge, out)) {
    ret = 0;
    goto done;
  }

  ret = fill_bitmap_commit(writer, &ent, merge, &queue, &tree_queue,
         old_bitmap, mapping);

  if (!ret)
    *out = bitmap_to_ewah(ent.bitmap);

done:
  bitmap_free(ent.bitmap);
  clear_prio_queue(&queue);
  clear_prio_queue(&tree_queue);

  return ret;
}

static int build_pseudo_merge_bitmaps(struct bitmap_writer *writer,
              struct bitmap_index *old_bitmap,
              const uint32_t *mapping,
              int *nr_stored)
{
  size_t i = bitmap_writer_nr_selected_commits(writer);
  int ret = 0;

  if (!writer->pseudo_merges_nr)
    return 0;

  trace2_region_enter("pack-bitmap-write", "building_pseudo_merge_bitmaps",
          writer->repo);

  for (; i < writer->selected_nr; i++) {
    struct bitmapped_commit *merge = &writer->selected[i];
    struct commit_list *p;
    struct bitmap *parents = bitmap_new();
    struct ewah_bitmap *objects = NULL;

    if (!merge->pseudo_merge)
      BUG("found non-pseudo merge commit at %"PRIuMAX,
          (uintmax_t)i);

    for (p = merge->commit->parents; p; p = p->next) {
      int found;
      uint32_t pos = find_object_pos(writer,
                   &p->item->object.oid,
                   &found);
      if (!found) {
        bitmap_free(parents);
        ret = -1;
        goto done;
      }
      bitmap_set(parents, pos);
    }

    merge->pseudo_merge_parents = bitmap_to_ewah(parents);
    bitmap_free(parents);

    if (build_pseudo_merge_bitmap(writer, old_bitmap, mapping,
                merge->commit, &objects) < 0) {
      ret = -1;
      goto done;
    }
    merge->bitmap = objects;

    (*nr_stored)++;
    display_progress(writer->progress, *nr_stored);
  }

done:
  trace2_region_leave("pack-bitmap-write", "building_pseudo_merge_bitmaps",
          writer->repo);

  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "pseudo_merge_bitmap_nr",
         pseudo_merge_bitmap_nr);
  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "building_bitmaps_pseudo_merge_reused",
         reused_pseudo_merge_bitmaps_nr);
  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "pseudo_merge_bitmap_parents",
         pseudo_merge_bitmap_parents);

  return ret;
}

static void store_selected(struct bitmap_writer *writer,
         struct bb_commit *ent, struct commit *commit)
{
  struct bitmapped_commit *stored = &writer->selected[ent->idx];
  khiter_t hash_pos;

  stored->bitmap = bitmap_to_ewah(ent->bitmap);

  if (ent->pseudo_merge)
    return;

  hash_pos = kh_get_oid_map(writer->bitmaps, commit->object.oid);
  if (hash_pos == kh_end(writer->bitmaps))
    die(_("attempted to store non-selected commit: '%s'"),
        oid_to_hex(&commit->object.oid));

  kh_value(writer->bitmaps, hash_pos) = stored;
}

int bitmap_writer_build(struct bitmap_writer *writer)
{
  struct bitmap_builder bb;
  size_t i;
  int nr_stored = 0; /* for progress */
  struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
  struct prio_queue tree_queue = { NULL };
  struct bitmap_index *old_bitmap;
  uint32_t *mapping = NULL;
  int closed = 1; /* until proven otherwise */

  if (writer->show_progress)
    writer->progress = start_progress(writer->repo,
              "Building bitmaps",
              writer->selected_nr);

  writer->pos_cache_hits = 0;
  writer->pos_cache_misses = 0;

  trace2_region_enter("pack-bitmap-write", "building_bitmaps_total",
          writer->repo);

  old_bitmap = prepare_bitmap_git(writer->to_pack->repo);
  if (old_bitmap)
    mapping = create_bitmap_mapping(old_bitmap, writer->to_pack);
  else
    mapping = NULL;

  bitmap_builder_init(&bb, writer, old_bitmap);
  for (i = bb.commits.nr; i > 0; i--) {
    struct commit *commit = bb.commits.items[i-1];
    struct bb_commit *ent = bb_data_at(&bb.data, commit);
    struct commit *child;
    int reused = 0;

    if (fill_bitmap_commit(writer, ent, commit, &queue, &tree_queue,
               old_bitmap, mapping) < 0) {
      closed = 0;
      break;
    }

    if (ent->selected) {
      store_selected(writer, ent, commit);
      nr_stored++;
      display_progress(writer->progress, nr_stored);
    }

    while ((child = pop_commit(&ent->reverse_edges))) {
      struct bb_commit *child_ent =
        bb_data_at(&bb.data, child);

      if (child_ent->bitmap)
        bitmap_or(child_ent->bitmap, ent->bitmap);
      else if (reused)
        child_ent->bitmap = bitmap_dup(ent->bitmap);
      else {
        child_ent->bitmap = ent->bitmap;
        reused = 1;
      }
    }
    if (!reused)
      bitmap_free(ent->bitmap);
    ent->bitmap = NULL;
  }
  if (closed &&
      build_pseudo_merge_bitmaps(writer, old_bitmap, mapping,
               &nr_stored) < 0)
    closed = 0;
  clear_prio_queue(&queue);
  clear_prio_queue(&tree_queue);
  bitmap_builder_clear(&bb);
  free_bitmap_index(old_bitmap);
  free(mapping);

  trace2_region_leave("pack-bitmap-write", "building_bitmaps_total",
          writer->repo);
  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "building_bitmaps_reused", reused_bitmaps_nr);
  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "fill_bitmap_commit_calls_nr",
         fill_bitmap_commit_calls_nr);
  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "fill_bitmap_commit_found_ancestor_nr",
         fill_bitmap_commit_found_ancestor_nr);
  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "bitmap_pos_cache_hits", writer->pos_cache_hits);
  trace2_data_intmax("pack-bitmap-write", writer->repo,
         "bitmap_pos_cache_misses", writer->pos_cache_misses);

  stop_progress(&writer->progress);

  if (closed)
    compute_xor_offsets(writer);
  return closed ? 0 : -1;
}

/**
 * Select the commits that will be bitmapped
 */
static inline unsigned int next_commit_index(unsigned int idx)
{
  static const unsigned int MIN_COMMITS = 100;
  static const unsigned int MAX_COMMITS = 5000;

  static const unsigned int MUST_REGION = 100;
  static const unsigned int MIN_REGION = 20000;

  unsigned int offset, next;

  if (idx <= MUST_REGION)
    return 0;

  if (idx <= MIN_REGION) {
    offset = idx - MUST_REGION;
    return (offset < MIN_COMMITS) ? offset : MIN_COMMITS;
  }

  offset = idx - MIN_REGION;
  next = (offset < MAX_COMMITS) ? offset : MAX_COMMITS;

  return (next > MIN_COMMITS) ? next : MIN_COMMITS;
}

static int date_compare(const void *_a, const void *_b)
{
  struct commit *a = *(struct commit **)_a;
  struct commit *b = *(struct commit **)_b;
  return (long)b->date - (long)a->date;
}

void bitmap_writer_select_commits(struct bitmap_writer *writer,
          struct commit **indexed_commits,
          unsigned int indexed_commits_nr)
{
  unsigned int i = 0, j, next;

  QSORT(indexed_commits, indexed_commits_nr, date_compare);

  if (indexed_commits_nr < 100) {
    for (i = 0; i < indexed_commits_nr; ++i)
      bitmap_writer_push_commit(writer, indexed_commits[i], 0);

    select_pseudo_merges(writer);

    return;
  }

  if (writer->show_progress)
    writer->progress = start_progress(writer->repo,
              "Selecting bitmap commits", 0);

  for (;;) {
    struct commit *chosen = NULL;

    next = next_commit_index(i);

    if (i + next >= indexed_commits_nr)
      break;

    if (next == 0) {
      chosen = indexed_commits[i];
    } else {
      chosen = indexed_commits[i + next];

      for (j = 0; j <= next; ++j) {
        struct commit *cm = indexed_commits[i + j];

        if ((cm->object.flags & NEEDS_BITMAP) != 0) {
          chosen = cm;
          break;
        }

        if (cm->parents && cm->parents->next)
          chosen = cm;
      }
    }

    bitmap_writer_push_commit(writer, chosen, 0);

    i += next + 1;
    display_progress(writer->progress, i);
  }

  stop_progress(&writer->progress);

  select_pseudo_merges(writer);
}


static int hashwrite_ewah_helper(void *f, const void *buf, size_t len)
{
  /* hashwrite will die on error */
  hashwrite(f, buf, len);
  return len;
}

/**
 * Write the bitmap index to disk
 */
static inline void dump_bitmap(struct hashfile *f, struct ewah_bitmap *bitmap)
{
  if (ewah_serialize_to(bitmap, hashwrite_ewah_helper, f) < 0)
    die("Failed to write bitmap index");
}

static const struct object_id *oid_access(size_t pos, const void *table)
{
  const struct pack_idx_entry * const *index = table;
  return &index[pos]->oid;
}

static void write_selected_commits_v1(struct bitmap_writer *writer,
              struct hashfile *f, off_t *offsets)
{
  int i;

  for (i = 0; i < bitmap_writer_nr_selected_commits(writer); ++i) {
    struct bitmapped_commit *stored = &writer->selected[i];
    if (stored->pseudo_merge)
      BUG("unexpected pseudo-merge among selected: %s",
          oid_to_hex(&stored->commit->object.oid));

    if (offsets)
      offsets[i] = hashfile_total(f);

    hashwrite_be32(f, stored->commit_pos);
    hashwrite_u8(f, stored->xor_offset);
    hashwrite_u8(f, stored->flags);

    dump_bitmap(f, stored->write_as);
  }
}

static int pseudo_merge_commit_pos_cmp(const void *_va, const void *_vb,
               void *_data)
{
  struct bitmap_writer *writer = _data;
  uint32_t pos_a = find_object_pos(writer, _va, NULL);
  uint32_t pos_b = find_object_pos(writer, _vb, NULL);

  if (pos_a < pos_b)
    return -1;
  if (pos_a > pos_b)
    return 1;
  return 0;
}

static void write_pseudo_merges(struct bitmap_writer *writer,
        struct hashfile *f)
{
  struct oid_array commits = OID_ARRAY_INIT;
  off_t *pseudo_merge_ofs = NULL;
  off_t start, table_start, next_ext;

  uint32_t base = bitmap_writer_nr_selected_commits(writer);
  size_t i, j = 0;

  CALLOC_ARRAY(pseudo_merge_ofs, writer->pseudo_merges_nr);

  start = hashfile_total(f);

  for (i = 0; i < writer->pseudo_merges_nr; i++) {
    struct bitmapped_commit *merge = &writer->selected[base + i];

    if (!merge->pseudo_merge)
      BUG("found non-pseudo merge commit at %"PRIuMAX, (uintmax_t)i);

    if (!merge->pseudo_merge_parents || !merge->bitmap)
      BUG("missing pseudo-merge bitmap for commit %s",
          oid_to_hex(&merge->commit->object.oid));

    pseudo_merge_ofs[i] = hashfile_total(f);
    dump_bitmap(f, merge->pseudo_merge_parents);
    dump_bitmap(f, merge->bitmap);
  }

  next_ext = st_add(hashfile_total(f),
        st_mult(kh_size(writer->pseudo_merge_commits),
          sizeof(uint32_t) + sizeof(uint64_t)));

  table_start = hashfile_total(f);

  commits.alloc = kh_size(writer->pseudo_merge_commits);
  CALLOC_ARRAY(commits.oid, commits.alloc);

  for (i = kh_begin(writer->pseudo_merge_commits); i != kh_end(writer->pseudo_merge_commits); i++) {
    if (!kh_exist(writer->pseudo_merge_commits, i))
      continue;
    oid_array_append(&commits, &kh_key(writer->pseudo_merge_commits, i));
  }

  /*
   * Sort the commits by their bit position so that the lookup
   * table can be binary searched by the reader (see
   * find_pseudo_merge()).
   */
  QSORT_S(commits.oid, commits.nr, pseudo_merge_commit_pos_cmp, writer);

  /* write lookup table (non-extended) */
  for (i = 0; i < commits.nr; i++) {
    int hash_pos;
    struct pseudo_merge_commit_idx *c;

    hash_pos = kh_get_oid_map(writer->pseudo_merge_commits,
            commits.oid[i]);
    if (hash_pos == kh_end(writer->pseudo_merge_commits))
      BUG("could not find pseudo-merge commit %s",
          oid_to_hex(&commits.oid[i]));

    c = kh_value(writer->pseudo_merge_commits, hash_pos);

    hashwrite_be32(f, find_object_pos(writer, &commits.oid[i],
              NULL));
    if (c->nr == 1)
      hashwrite_be64(f, pseudo_merge_ofs[c->pseudo_merge[0]]);
    else if (c->nr > 1) {
      if (next_ext & ((uint64_t)1<<63))
        die(_("too many pseudo-merges"));
      hashwrite_be64(f, next_ext | ((uint64_t)1<<63));
      next_ext = st_add3(next_ext,
             sizeof(uint32_t),
             st_mult(c->nr, sizeof(uint64_t)));
    } else
      BUG("expected commit '%s' to have at least one "
          "pseudo-merge", oid_to_hex(&commits.oid[i]));
  }

  /* write lookup table (extended) */
  for (i = 0; i < commits.nr; i++) {
    int hash_pos;
    struct pseudo_merge_commit_idx *c;

    hash_pos = kh_get_oid_map(writer->pseudo_merge_commits,
            commits.oid[i]);
    if (hash_pos == kh_end(writer->pseudo_merge_commits))
      BUG("could not find pseudo-merge commit %s",
          oid_to_hex(&commits.oid[i]));

    c = kh_value(writer->pseudo_merge_commits, hash_pos);
    if (c->nr == 1)
      continue;

    hashwrite_be32(f, c->nr);
    for (j = 0; j < c->nr; j++)
      hashwrite_be64(f, pseudo_merge_ofs[c->pseudo_merge[j]]);
  }

  /* write positions for all pseudo merges */
  for (i = 0; i < writer->pseudo_merges_nr; i++)
    hashwrite_be64(f, pseudo_merge_ofs[i]);

  hashwrite_be32(f, writer->pseudo_merges_nr);
  hashwrite_be32(f, kh_size(writer->pseudo_merge_commits));
  hashwrite_be64(f, table_start - start);
  hashwrite_be64(f, hashfile_total(f) - start + sizeof(uint64_t));

  oid_array_clear(&commits);
  free(pseudo_merge_ofs);
}

static int table_cmp(const void *_va, const void *_vb, void *_data)
{
  struct bitmap_writer *writer = _data;
  struct bitmapped_commit *a = &writer->selected[*(uint32_t *)_va];
  struct bitmapped_commit *b = &writer->selected[*(uint32_t *)_vb];

  if (a->commit_pos < b->commit_pos)
    return -1;
  else if (a->commit_pos > b->commit_pos)
    return 1;

  return 0;
}

static void write_lookup_table(struct bitmap_writer *writer, struct hashfile *f,
             off_t *offsets)
{
  uint32_t i;
  uint32_t *table, *table_inv;

  ALLOC_ARRAY(table, bitmap_writer_nr_selected_commits(writer));
  ALLOC_ARRAY(table_inv, bitmap_writer_nr_selected_commits(writer));

  for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++)
    table[i] = i;

  /*
   * At the end of this sort table[j] = i means that the i'th
   * bitmap corresponds to j'th bitmapped commit (among the selected
   * commits) in lex order of OIDs.
   */
  QSORT_S(table, bitmap_writer_nr_selected_commits(writer), table_cmp, writer);

  /* table_inv helps us discover that relationship (i'th bitmap
   * to j'th commit by j = table_inv[i])
   */
  for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++)
    table_inv[table[i]] = i;

  trace2_region_enter("pack-bitmap-write", "writing_lookup_table", writer->repo);
  for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) {
    struct bitmapped_commit *selected = &writer->selected[table[i]];
    uint32_t xor_offset = selected->xor_offset;
    uint32_t xor_row;

    if (xor_offset) {
      /*
       * xor_index stores the index (in the bitmap entries)
       * of the corresponding xor bitmap. But we need to convert
       * this index into lookup table's index. So, table_inv[xor_index]
       * gives us the index position w.r.t. the lookup table.
       *
       * If "k = table[i] - xor_offset" then the xor base is the k'th
       * bitmap. `table_inv[k]` gives us the position of that bitmap
       * in the lookup table.
       */
      uint32_t xor_index = table[i] - xor_offset;
      xor_row = table_inv[xor_index];
    } else {
      xor_row = 0xffffffff;
    }

    hashwrite_be32(f, writer->selected[table[i]].commit_pos);
    hashwrite_be64(f, (uint64_t)offsets[table[i]]);
    hashwrite_be32(f, xor_row);
  }
  trace2_region_leave("pack-bitmap-write", "writing_lookup_table", writer->repo);

  free(table);
  free(table_inv);
}

static void write_hash_cache(struct hashfile *f,
           struct pack_idx_entry **index,
           uint32_t index_nr)
{
  uint32_t i;

  for (i = 0; i < index_nr; ++i) {
    struct object_entry *entry = (struct object_entry *)index[i];
    hashwrite_be32(f, entry->hash);
  }
}

void bitmap_writer_set_checksum(struct bitmap_writer *writer,
        const unsigned char *sha1)
{
  hashcpy(writer->pack_checksum, sha1, writer->repo->hash_algo);
}

void bitmap_writer_finish(struct bitmap_writer *writer,
        struct pack_idx_entry **index,
        const char *filename,
        uint16_t options)
{
  static uint16_t default_version = 1;
  static uint16_t flags = BITMAP_OPT_FULL_DAG;
  struct strbuf tmp_file = STRBUF_INIT;
  struct hashfile *f;
  off_t *offsets = NULL;
  uint32_t i, base_objects;

  struct bitmap_disk_header header;

  int fd = odb_mkstemp(writer->repo->objects, &tmp_file,
           "pack/tmp_bitmap_XXXXXX");

  if (writer->pseudo_merges_nr)
    options |= BITMAP_OPT_PSEUDO_MERGES;

  f = hashfd(writer->repo->hash_algo, fd, tmp_file.buf);

  memcpy(header.magic, BITMAP_IDX_SIGNATURE, sizeof(BITMAP_IDX_SIGNATURE));
  header.version = htons(default_version);
  header.options = htons(flags | options);
  header.entry_count = htonl(bitmap_writer_nr_selected_commits(writer));
  hashcpy(header.checksum, writer->pack_checksum, writer->repo->hash_algo);

  hashwrite(f, &header, sizeof(header) - GIT_MAX_RAWSZ + writer->repo->hash_algo->rawsz);
  dump_bitmap(f, writer->commits);
  dump_bitmap(f, writer->trees);
  dump_bitmap(f, writer->blobs);
  dump_bitmap(f, writer->tags);

  if (options & BITMAP_OPT_LOOKUP_TABLE)
    CALLOC_ARRAY(offsets, writer->to_pack->nr_objects);

  if (writer->midx)
    base_objects = writer->midx->num_objects +
      writer->midx->num_objects_in_base;
  else
    base_objects = 0;

  for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) {
    struct bitmapped_commit *stored = &writer->selected[i];
    int commit_pos = oid_pos(&stored->commit->object.oid, index,
           writer->to_pack->nr_objects,
           oid_access);

    if (commit_pos < 0)
      BUG("trying to write commit not in index");
    stored->commit_pos = commit_pos + base_objects;
  }

  write_selected_commits_v1(writer, f, offsets);

  if (options & BITMAP_OPT_PSEUDO_MERGES)
    write_pseudo_merges(writer, f);

  if (options & BITMAP_OPT_LOOKUP_TABLE)
    write_lookup_table(writer, f, offsets);

  if (options & BITMAP_OPT_HASH_CACHE)
    write_hash_cache(f, index, writer->to_pack->nr_objects);

  finalize_hashfile(f, NULL, FSYNC_COMPONENT_PACK_METADATA,
        CSUM_HASH_IN_STREAM | CSUM_FSYNC | CSUM_CLOSE);

  if (adjust_shared_perm(writer->repo, tmp_file.buf))
    die_errno("unable to make temporary bitmap file readable");

  if (rename(tmp_file.buf, filename))
    die_errno("unable to rename temporary bitmap file to '%s'", filename);

  strbuf_release(&tmp_file);
  free(offsets);
}

Coverage Report

Created: 2026-10-17 07:15