[thirdparty/git.git] / pack-bitmap.h

#ifndef PACK_BITMAP_H
#define PACK_BITMAP_H

#include "ewah/ewok.h"
#include "khash.h"
#include "pack.h"
#include "pack-objects.h"
#include "string-list.h"

struct commit;
struct repository;
struct rev_info;

static const char BITMAP_IDX_SIGNATURE[] = {'B', 'I', 'T', 'M'};

struct bitmap_disk_header {
	char magic[ARRAY_SIZE(BITMAP_IDX_SIGNATURE)];
	uint16_t version;
	uint16_t options;
	uint32_t entry_count;
	unsigned char checksum[GIT_MAX_RAWSZ];
};

#define BITMAP_PSEUDO_MERGE (1u<<21)
#define NEEDS_BITMAP (1u<<22)

/*
 * The width in bytes of a single triplet in the lookup table
 * extension:
 *     (commit_pos, offset, xor_row)
 *
 * whose fields ar 32-, 64-, 32- bits wide, respectively.
 */
#define BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH (16)

enum pack_bitmap_opts {
	BITMAP_OPT_FULL_DAG = 0x1,
	BITMAP_OPT_HASH_CACHE = 0x4,
	BITMAP_OPT_LOOKUP_TABLE = 0x10,
	BITMAP_OPT_PSEUDO_MERGES = 0x20,
};

enum pack_bitmap_flags {
	BITMAP_FLAG_REUSE = 0x1
};

typedef int (*show_reachable_fn)(
	const struct object_id *oid,
	enum object_type type,
	int flags,
	uint32_t hash,
	struct packed_git *found_pack,
	off_t found_offset,
	void *payload);

struct bitmap_index;

struct bitmapped_pack {
	struct packed_git *p;

	uint32_t bitmap_pos;
	uint32_t bitmap_nr;

	struct multi_pack_index *from_midx; /* MIDX only */
	uint32_t pack_int_id; /* MIDX only */
};

struct bitmap_index *prepare_bitmap_git(struct repository *r);
struct bitmap_index *prepare_midx_bitmap_git(struct multi_pack_index *midx);

/*
 * Given a bitmap index, determine whether it contains the pack either directly
 * or via the multi-pack-index.
 */
int bitmap_index_contains_pack(struct bitmap_index *bitmap, struct packed_git *pack);

void count_bitmap_commit_list(struct bitmap_index *, uint32_t *commits,
			      uint32_t *trees, uint32_t *blobs, uint32_t *tags);
void traverse_bitmap_commit_list(struct bitmap_index *,
				 struct rev_info *revs,
				 show_reachable_fn show_reachable);
void test_bitmap_walk(struct rev_info *revs);
int test_bitmap_commits(struct repository *r);
int test_bitmap_hashes(struct repository *r);
int test_bitmap_pseudo_merges(struct repository *r);
int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n);
int test_bitmap_pseudo_merge_objects(struct repository *r, uint32_t n);

struct list_objects_filter_options;

/*
 * Filter bitmapped objects and iterate through all resulting objects,
 * executing `show_reach` for each of them. Returns `-1` in case the filter is
 * not supported, `0` otherwise.
 */
int for_each_bitmapped_object(struct bitmap_index *bitmap_git,
			      struct list_objects_filter_options *filter,
			      show_reachable_fn show_reach,
			      void *payload);

#define GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL \
	"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL"

struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs,
					 int filter_provided_objects);
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 rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping,
			     kh_oid_map_t *reused_bitmaps, int show_progress);
void free_bitmap_index(struct bitmap_index *);
int bitmap_walk_contains(struct bitmap_index *,
			 struct bitmap *bitmap, const struct object_id *oid);

/*
 * After a traversal has been performed by prepare_bitmap_walk(), this can be
 * queried to see if a particular object was reachable from any of the
 * objects flagged as UNINTERESTING.
 */
int bitmap_has_oid_in_uninteresting(struct bitmap_index *, const struct object_id *oid);

off_t get_disk_usage_from_bitmap(struct bitmap_index *, struct rev_info *);

struct bitmap_writer {
	struct repository *repo;
	struct ewah_bitmap *commits;
	struct ewah_bitmap *trees;
	struct ewah_bitmap *blobs;
	struct ewah_bitmap *tags;

	kh_oid_map_t *bitmaps;
	struct packing_data *to_pack;
	struct multi_pack_index *midx; /* if appending to a MIDX chain */

	struct bitmapped_commit *selected;
	unsigned int selected_nr, selected_alloc;

	struct string_list pseudo_merge_groups;
	kh_oid_map_t *pseudo_merge_commits; /* oid -> pseudo merge(s) */
	uint32_t pseudo_merges_nr;

	struct progress *progress;
	int show_progress;
	unsigned char pack_checksum[GIT_MAX_RAWSZ];
};

void bitmap_writer_init(struct bitmap_writer *writer, struct repository *r,
			struct packing_data *pdata,
			struct multi_pack_index *midx);
void bitmap_writer_show_progress(struct bitmap_writer *writer, int show);
void bitmap_writer_set_checksum(struct bitmap_writer *writer,
				const unsigned char *sha1);
void bitmap_writer_build_type_index(struct bitmap_writer *writer,
				    struct pack_idx_entry **index);
int bitmap_writer_has_bitmapped_object_id(struct bitmap_writer *writer,
					  const struct object_id *oid);
void bitmap_writer_push_commit(struct bitmap_writer *writer,
			       struct commit *commit, unsigned pseudo_merge);
uint32_t *create_bitmap_mapping(struct bitmap_index *bitmap_git,
				struct packing_data *mapping);
int rebuild_bitmap(const uint32_t *reposition,
		   struct ewah_bitmap *source,
		   struct bitmap *dest);
struct ewah_bitmap *bitmap_for_commit(struct bitmap_index *bitmap_git,
				      struct commit *commit);
struct ewah_bitmap *pseudo_merge_bitmap_for_commit(struct bitmap_index *bitmap_git,
						   struct commit *commit);
void bitmap_writer_select_commits(struct bitmap_writer *writer,
				  struct commit **indexed_commits,
				  unsigned int indexed_commits_nr);
int bitmap_writer_build(struct bitmap_writer *writer);
void bitmap_writer_finish(struct bitmap_writer *writer,
			  struct pack_idx_entry **index,
			  const char *filename,
			  uint16_t options);
void bitmap_writer_free(struct bitmap_writer *writer);
char *midx_bitmap_filename(struct multi_pack_index *midx);
char *pack_bitmap_filename(struct packed_git *p);

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);

int verify_bitmap_files(struct repository *r);

struct ewah_bitmap *read_bitmap(const unsigned char *map,
				size_t map_size, size_t *map_pos);
#endif
Commit	Line	Data
	1	#ifndef PACK_BITMAP_H
	2	#define PACK_BITMAP_H
	3
	4	#include "ewah/ewok.h"
	5	#include "khash.h"
	6	#include "pack.h"
	7	#include "pack-objects.h"
	8	#include "string-list.h"
	9
	10	struct commit;
	11	struct repository;
	12	struct rev_info;
	13
	14	static const char BITMAP_IDX_SIGNATURE[] = {'B', 'I', 'T', 'M'};
	15
	16	struct bitmap_disk_header {
	17	char magic[ARRAY_SIZE(BITMAP_IDX_SIGNATURE)];
	18	uint16_t version;
	19	uint16_t options;
	20	uint32_t entry_count;
	21	unsigned char checksum[GIT_MAX_RAWSZ];
	22	};
	23
	24	#define BITMAP_PSEUDO_MERGE (1u<<21)
	25	#define NEEDS_BITMAP (1u<<22)
	26
	27	/*
	28	* The width in bytes of a single triplet in the lookup table
	29	* extension:
	30	* (commit_pos, offset, xor_row)
	31	*
	32	* whose fields ar 32-, 64-, 32- bits wide, respectively.
	33	*/
	34	#define BITMAP_LOOKUP_TABLE_TRIPLET_WIDTH (16)
	35
	36	enum pack_bitmap_opts {
	37	BITMAP_OPT_FULL_DAG = 0x1,
	38	BITMAP_OPT_HASH_CACHE = 0x4,
	39	BITMAP_OPT_LOOKUP_TABLE = 0x10,
	40	BITMAP_OPT_PSEUDO_MERGES = 0x20,
	41	};
	42
	43	enum pack_bitmap_flags {
	44	BITMAP_FLAG_REUSE = 0x1
	45	};
	46
	47	typedef int (*show_reachable_fn)(
	48	const struct object_id *oid,
	49	enum object_type type,
	50	int flags,
	51	uint32_t hash,
	52	struct packed_git *found_pack,
	53	off_t found_offset,
	54	void *payload);
	55
	56	struct bitmap_index;
	57
	58	struct bitmapped_pack {
	59	struct packed_git *p;
	60
	61	uint32_t bitmap_pos;
	62	uint32_t bitmap_nr;
	63
	64	struct multi_pack_index from_midx; / MIDX only */
	65	uint32_t pack_int_id; /* MIDX only */
	66	};
	67
	68	struct bitmap_index prepare_bitmap_git(struct repository r);
	69	struct bitmap_index prepare_midx_bitmap_git(struct multi_pack_index midx);
	70
	71	/*
	72	* Given a bitmap index, determine whether it contains the pack either directly
	73	* or via the multi-pack-index.
	74	*/
	75	int bitmap_index_contains_pack(struct bitmap_index bitmap, struct packed_git pack);
	76
	77	void count_bitmap_commit_list(struct bitmap_index , uint32_t commits,
	78	uint32_t trees, uint32_t blobs, uint32_t *tags);
	79	void traverse_bitmap_commit_list(struct bitmap_index *,
	80	struct rev_info *revs,
	81	show_reachable_fn show_reachable);
	82	void test_bitmap_walk(struct rev_info *revs);
	83	int test_bitmap_commits(struct repository *r);
	84	int test_bitmap_hashes(struct repository *r);
	85	int test_bitmap_pseudo_merges(struct repository *r);
	86	int test_bitmap_pseudo_merge_commits(struct repository *r, uint32_t n);
	87	int test_bitmap_pseudo_merge_objects(struct repository *r, uint32_t n);
	88
	89	struct list_objects_filter_options;
	90
	91	/*
	92	* Filter bitmapped objects and iterate through all resulting objects,
	93	* executing `show_reach` for each of them. Returns `-1` in case the filter is
	94	* not supported, `0` otherwise.
	95	*/
	96	int for_each_bitmapped_object(struct bitmap_index *bitmap_git,
	97	struct list_objects_filter_options *filter,
	98	show_reachable_fn show_reach,
	99	void *payload);
	100
	101	#define GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL \
	102	"GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL"
	103
	104	struct bitmap_index prepare_bitmap_walk(struct rev_info revs,
	105	int filter_provided_objects);
	106	void reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,
	107	struct bitmapped_pack **packs_out,
	108	size_t *packs_nr_out,
	109	struct bitmap **reuse_out,
	110	int multi_pack_reuse);
	111	int rebuild_existing_bitmaps(struct bitmap_index , struct packing_data mapping,
	112	kh_oid_map_t *reused_bitmaps, int show_progress);
	113	void free_bitmap_index(struct bitmap_index *);
	114	int bitmap_walk_contains(struct bitmap_index *,
	115	struct bitmap bitmap, const struct object_id oid);
	116
	117	/*
	118	* After a traversal has been performed by prepare_bitmap_walk(), this can be
	119	* queried to see if a particular object was reachable from any of the
	120	* objects flagged as UNINTERESTING.
	121	*/
	122	int bitmap_has_oid_in_uninteresting(struct bitmap_index , const struct object_id oid);
	123
	124	off_t get_disk_usage_from_bitmap(struct bitmap_index , struct rev_info );
	125
	126	struct bitmap_writer {
	127	struct repository *repo;
	128	struct ewah_bitmap *commits;
	129	struct ewah_bitmap *trees;
	130	struct ewah_bitmap *blobs;
	131	struct ewah_bitmap *tags;
	132
	133	kh_oid_map_t *bitmaps;
	134	struct packing_data *to_pack;
	135	struct multi_pack_index midx; / if appending to a MIDX chain */
	136
	137	struct bitmapped_commit *selected;
	138	unsigned int selected_nr, selected_alloc;
	139
	140	struct string_list pseudo_merge_groups;
	141	kh_oid_map_t pseudo_merge_commits; / oid -> pseudo merge(s) */
	142	uint32_t pseudo_merges_nr;
	143
	144	struct progress *progress;
	145	int show_progress;
	146	unsigned char pack_checksum[GIT_MAX_RAWSZ];
	147	};
	148
	149	void bitmap_writer_init(struct bitmap_writer writer, struct repository r,
	150	struct packing_data *pdata,
	151	struct multi_pack_index *midx);
	152	void bitmap_writer_show_progress(struct bitmap_writer *writer, int show);
	153	void bitmap_writer_set_checksum(struct bitmap_writer *writer,
	154	const unsigned char *sha1);
	155	void bitmap_writer_build_type_index(struct bitmap_writer *writer,
	156	struct pack_idx_entry **index);
	157	int bitmap_writer_has_bitmapped_object_id(struct bitmap_writer *writer,
	158	const struct object_id *oid);
	159	void bitmap_writer_push_commit(struct bitmap_writer *writer,
	160	struct commit *commit, unsigned pseudo_merge);
	161	uint32_t create_bitmap_mapping(struct bitmap_index bitmap_git,
	162	struct packing_data *mapping);
	163	int rebuild_bitmap(const uint32_t *reposition,
	164	struct ewah_bitmap *source,
	165	struct bitmap *dest);
	166	struct ewah_bitmap bitmap_for_commit(struct bitmap_index bitmap_git,
	167	struct commit *commit);
	168	struct ewah_bitmap pseudo_merge_bitmap_for_commit(struct bitmap_index bitmap_git,
	169	struct commit *commit);
	170	void bitmap_writer_select_commits(struct bitmap_writer *writer,
	171	struct commit **indexed_commits,
	172	unsigned int indexed_commits_nr);
	173	int bitmap_writer_build(struct bitmap_writer *writer);
	174	void bitmap_writer_finish(struct bitmap_writer *writer,
	175	struct pack_idx_entry **index,
	176	const char *filename,
	177	uint16_t options);
	178	void bitmap_writer_free(struct bitmap_writer *writer);
	179	char midx_bitmap_filename(struct multi_pack_index midx);
	180	char pack_bitmap_filename(struct packed_git p);
	181
	182	int bitmap_is_midx(struct bitmap_index *bitmap_git);
	183
	184	const struct string_list bitmap_preferred_tips(struct repository r);
	185	int bitmap_is_preferred_refname(struct repository r, const char refname);
	186
	187	int verify_bitmap_files(struct repository *r);
	188
	189	struct ewah_bitmap read_bitmap(const unsigned char map,
	190	size_t map_size, size_t *map_pos);
	191	#endif