git/pack-bitmap.c

#define USE_THE_REPOSITORY_VARIABLE

#include "git-compat-util.h"
#include "commit.h"
#include "gettext.h"
#include "hex.h"
#include "strbuf.h"
#include "tag.h"
#include "diff.h"
#include "revision.h"
#include "progress.h"
#include "list-objects.h"
#include "pack.h"
#include "pack-bitmap.h"
#include "pack-revindex.h"
#include "pack-objects.h"
#include "packfile.h"
#include "repository.h"
#include "trace2.h"
#include "object-file.h"
#include "object-store-ll.h"
#include "list-objects-filter-options.h"
#include "midx.h"
#include "config.h"
#include "pseudo-merge.h"

/*
 * An entry on the bitmap index, representing the bitmap for a given
 * commit.
 */
struct stored_bitmap { … };

/*
 * The active bitmap index for a repository. By design, repositories only have
 * a single bitmap index available (the index for the biggest packfile in
 * the repository), since bitmap indexes need full closure.
 *
 * If there is more than one bitmap index available (e.g. because of alternates),
 * the active bitmap index is the largest one.
 */
struct bitmap_index { … };

static int pseudo_merges_satisfied_nr;
static int pseudo_merges_cascades_nr;
static int existing_bitmaps_hits_nr;
static int existing_bitmaps_misses_nr;
static int roots_with_bitmaps_nr;
static int roots_without_bitmaps_nr;

static struct ewah_bitmap *lookup_stored_bitmap(struct stored_bitmap *st)
{ … }

struct ewah_bitmap *read_bitmap(const unsigned char *map,
				size_t map_size, size_t *map_pos)
{ … }

/*
 * Read a bitmap from the current read position on the mmaped
 * index, and increase the read position accordingly
 */
static struct ewah_bitmap *read_bitmap_1(struct bitmap_index *index)
{ … }

static uint32_t bitmap_num_objects(struct bitmap_index *index)
{ … }

static int load_bitmap_header(struct bitmap_index *index)
{ … }

static struct stored_bitmap *store_bitmap(struct bitmap_index *index,
					  struct ewah_bitmap *root,
					  const struct object_id *oid,
					  struct stored_bitmap *xor_with,
					  int flags)
{ … }

static inline uint32_t read_be32(const unsigned char *buffer, size_t *pos)
{ … }

static inline uint8_t read_u8(const unsigned char *buffer, size_t *pos)
{ … }

#define MAX_XOR_OFFSET …

static int nth_bitmap_object_oid(struct bitmap_index *index,
				 struct object_id *oid,
				 uint32_t n)
{ … }

static int load_bitmap_entries_v1(struct bitmap_index *index)
{ … }

char *midx_bitmap_filename(struct multi_pack_index *midx)
{ … }

char *pack_bitmap_filename(struct packed_git *p)
{ … }

static int open_midx_bitmap_1(struct bitmap_index *bitmap_git,
			      struct multi_pack_index *midx)
{ … }

static int open_pack_bitmap_1(struct bitmap_index *bitmap_git, struct packed_git *packfile)
{ … }

static int load_reverse_index(struct repository *r, struct bitmap_index *bitmap_git)
{ … }

static int load_bitmap(struct repository *r, struct bitmap_index *bitmap_git)
{ … }

static int open_pack_bitmap(struct repository *r,
			    struct bitmap_index *bitmap_git)
{ … }

static int open_midx_bitmap(struct repository *r,
			    struct bitmap_index *bitmap_git)
{ … }

static int open_bitmap(struct repository *r,
		       struct bitmap_index *bitmap_git)
{ … }

struct bitmap_index *prepare_bitmap_git(struct repository *r)
{ … }

struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx)
{ … }

struct include_data { … };

struct bitmap_lookup_table_triplet { … };

struct bitmap_lookup_table_xor_item { … };

/*
 * Given a `triplet` struct pointer and pointer `p`, this
 * function reads the triplet beginning at `p` into the struct.
 * Note that this function assumes that there is enough memory
 * left for filling the `triplet` struct from `p`.
 */
static int bitmap_lookup_table_get_triplet_by_pointer(struct bitmap_lookup_table_triplet *triplet,
						      const unsigned char *p)
{ … }

/*
 * This function gets the raw triplet from `row`'th row in the
 * lookup table and fills that data to the `triplet`.
 */
static int bitmap_lookup_table_get_triplet(struct bitmap_index *bitmap_git,
					   uint32_t pos,
					   struct bitmap_lookup_table_triplet *triplet)
{ … }

/*
 * Searches for a matching triplet. `commit_pos` is a pointer
 * to the wanted commit position value. `table_entry` points to
 * a triplet in lookup table. The first 4 bytes of each
 * triplet (pointed by `table_entry`) are compared with `*commit_pos`.
 */
static int triplet_cmp(const void *commit_pos, const void *table_entry)
{ … }

static uint32_t bitmap_bsearch_pos(struct bitmap_index *bitmap_git,
			    struct object_id *oid,
			    uint32_t *result)
{ … }

/*
 * `bsearch_triplet_by_pos` function searches for the raw triplet
 * having commit position same as `commit_pos` and fills `triplet`
 * object from the raw triplet. Returns 1 on success and 0 on
 * failure.
 */
static int bitmap_bsearch_triplet_by_pos(uint32_t commit_pos,
				  struct bitmap_index *bitmap_git,
				  struct bitmap_lookup_table_triplet *triplet)
{ … }

static struct stored_bitmap *lazy_bitmap_for_commit(struct bitmap_index *bitmap_git,
						    struct commit *commit)
{ … }

struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
				      struct commit *commit)
{ … }

static inline int bitmap_position_extended(struct bitmap_index *bitmap_git,
					   const struct object_id *oid)
{ … }

static inline int bitmap_position_packfile(struct bitmap_index *bitmap_git,
					   const struct object_id *oid)
{ … }

static int bitmap_position_midx(struct bitmap_index *bitmap_git,
				const struct object_id *oid)
{ … }

static int bitmap_position(struct bitmap_index *bitmap_git,
			   const struct object_id *oid)
{ … }

static int ext_index_add_object(struct bitmap_index *bitmap_git,
				struct object *object, const char *name)
{ … }

struct bitmap_show_data { … };

static void show_object(struct object *object, const char *name, void *data_)
{ … }

static void show_commit(struct commit *commit UNUSED,
			void *data UNUSED)
{ … }

static unsigned apply_pseudo_merges_for_commit_1(struct bitmap_index *bitmap_git,
						 struct bitmap *result,
						 struct commit *commit,
						 uint32_t commit_pos)
{ … }

static int add_to_include_set(struct bitmap_index *bitmap_git,
			      struct include_data *data,
			      struct commit *commit,
			      int bitmap_pos)
{ … }

static int should_include(struct commit *commit, void *_data)
{ … }

static int should_include_obj(struct object *obj, void *_data)
{ … }

static int add_commit_to_bitmap(struct bitmap_index *bitmap_git,
				struct bitmap **base,
				struct commit *commit)
{ … }

static struct bitmap *fill_in_bitmap(struct bitmap_index *bitmap_git,
				     struct rev_info *revs,
				     struct bitmap *base,
				     struct bitmap *seen)
{ … }

struct bitmap_boundary_cb { … };

static void show_boundary_commit(struct commit *commit, void *_data)
{ … }

static void show_boundary_object(struct object *object UNUSED,
				 const char *name UNUSED,
				 void *data UNUSED)
{ … }

static unsigned cascade_pseudo_merges_1(struct bitmap_index *bitmap_git,
					struct bitmap *result,
					struct bitmap *roots)
{ … }

static struct bitmap *find_boundary_objects(struct bitmap_index *bitmap_git,
					    struct rev_info *revs,
					    struct object_list *roots)
{ … }

struct ewah_bitmap *pseudo_merge_bitmap_for_commit(struct bitmap_index *bitmap_git,
						   struct commit *commit)
{ … }

static void unsatisfy_all_pseudo_merges(struct bitmap_index *bitmap_git)
{ … }

static struct bitmap *find_objects(struct bitmap_index *bitmap_git,
				   struct rev_info *revs,
				   struct object_list *roots,
				   struct bitmap *seen)
{ … }

static void show_extended_objects(struct bitmap_index *bitmap_git,
				  struct rev_info *revs,
				  show_reachable_fn show_reach)
{ … }

static void init_type_iterator(struct ewah_iterator *it,
			       struct bitmap_index *bitmap_git,
			       enum object_type type)
{ … }

static void show_objects_for_type(
	struct bitmap_index *bitmap_git,
	enum object_type object_type,
	show_reachable_fn show_reach)
{ … }

static int in_bitmapped_pack(struct bitmap_index *bitmap_git,
			     struct object_list *roots)
{ … }

static struct bitmap *find_tip_objects(struct bitmap_index *bitmap_git,
				       struct object_list *tip_objects,
				       enum object_type type)
{ … }

static void filter_bitmap_exclude_type(struct bitmap_index *bitmap_git,
				       struct object_list *tip_objects,
				       struct bitmap *to_filter,
				       enum object_type type)
{ … }

static void filter_bitmap_blob_none(struct bitmap_index *bitmap_git,
				    struct object_list *tip_objects,
				    struct bitmap *to_filter)
{ … }

static unsigned long get_size_by_pos(struct bitmap_index *bitmap_git,
				     uint32_t pos)
{ … }

static void filter_bitmap_blob_limit(struct bitmap_index *bitmap_git,
				     struct object_list *tip_objects,
				     struct bitmap *to_filter,
				     unsigned long limit)
{ … }

static void filter_bitmap_tree_depth(struct bitmap_index *bitmap_git,
				     struct object_list *tip_objects,
				     struct bitmap *to_filter,
				     unsigned long limit)
{ … }

static void filter_bitmap_object_type(struct bitmap_index *bitmap_git,
				      struct object_list *tip_objects,
				      struct bitmap *to_filter,
				      enum object_type object_type)
{ … }

static int filter_bitmap(struct bitmap_index *bitmap_git,
			 struct object_list *tip_objects,
			 struct bitmap *to_filter,
			 struct list_objects_filter_options *filter)
{ … }

static int can_filter_bitmap(struct list_objects_filter_options *filter)
{ … }


static void filter_packed_objects_from_bitmap(struct bitmap_index *bitmap_git,
					      struct bitmap *result)
{ … }

struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
					 int filter_provided_objects)
{ … }

/*
 * -1 means "stop trying further objects"; 0 means we may or may not have
 * reused, but you can keep feeding bits.
 */
static int try_partial_reuse(struct bitmap_index *bitmap_git,
			     struct bitmapped_pack *pack,
			     size_t bitmap_pos,
			     uint32_t pack_pos,
			     off_t offset,
			     struct bitmap *reuse,
			     struct pack_window **w_curs)
{ … }

static void reuse_partial_packfile_from_bitmap_1(struct bitmap_index *bitmap_git,
						 struct bitmapped_pack *pack,
						 struct bitmap *reuse)
{ … }

static int bitmapped_pack_cmp(const void *va, const void *vb)
{ … }

void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
					struct bitmapped_pack **packs_out,
					size_t *packs_nr_out,
					struct bitmap **reuse_out,
					int multi_pack_reuse)
{ … }

int bitmap_walk_contains(struct bitmap_index *bitmap_git,
			 struct bitmap *bitmap, const struct object_id *oid)
{ … }

void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,
				 struct rev_info *revs,
				 show_reachable_fn show_reachable)
{ … }

static uint32_t count_object_type(struct bitmap_index *bitmap_git,
				  enum object_type type)
{ … }

void count_bitmap_commit_list(struct bitmap_index *bitmap_git,
			      uint32_t *commits, uint32_t *trees,
			      uint32_t *blobs, uint32_t *tags)
{ … }

struct bitmap_test_data { … };

static void test_bitmap_type(struct bitmap_test_data *tdata,
			     struct object *obj, int pos)
{ … }

static void test_show_object(struct object *object,
			     const char *name UNUSED,
			     void *data)
{ … }

static void test_show_commit(struct commit *commit, void *data)
{ … }

void test_bitmap_walk(struct rev_info *revs)
{ … }

int test_bitmap_commits(struct repository *r)
{ … }

int test_bitmap_hashes(struct repository *r)
{ … }

static void bit_pos_to_object_id(struct bitmap_index *bitmap_git,
				 uint32_t bit_pos,
				 struct object_id *oid)
{ … }

int test_bitmap_pseudo_merges(struct repository *r)
{ … }

static void dump_ewah_object_ids(struct bitmap_index *bitmap_git,
				 struct ewah_bitmap *bitmap)

{ … }

int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n)
{ … }

int test_bitmap_pseudo_merge_objects(struct repository *r, uint32_t n)
{ … }

int rebuild_bitmap(const uint32_t *reposition,
		   struct ewah_bitmap *source,
		   struct bitmap *dest)
{ … }

uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
				struct packing_data *mapping)
{ … }

void free_bitmap_index(struct bitmap_index *b)
{ … }

int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,
				    const struct object_id *oid)
{ … }

static off_t get_disk_usage_for_type(struct bitmap_index *bitmap_git,
				     enum object_type object_type)
{ … }

static off_t get_disk_usage_for_extended(struct bitmap_index *bitmap_git)
{ … }

off_t get_disk_usage_from_bitmap(struct bitmap_index *bitmap_git,
				 struct rev_info *revs)
{ … }

int bitmap_is_midx(struct bitmap_index *bitmap_git)
{ … }

const struct string_list *bitmap_preferred_tips(struct repository *r)
{ … }

int bitmap_is_preferred_refname(struct repository *r, const char *refname)
{ … }

static int verify_bitmap_file(const char *name)
{ … }

int verify_bitmap_files(struct repository *r)
{ … }