#include "hashmap.h"
#include "replace-object.h"
#include "progress.h"
+#include "bloom.h"
+#include "commit-slab.h"
#define GRAPH_SIGNATURE 0x43475048 /* "CGPH" */
#define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
#define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
#define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
#define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
+#define GRAPH_CHUNKID_BLOOMINDEXES 0x42494458 /* "BIDX" */
+#define GRAPH_CHUNKID_BLOOMDATA 0x42444154 /* "BDAT" */
#define GRAPH_CHUNKID_BASE 0x42415345 /* "BASE" */
+#define MAX_NUM_CHUNKS 7
#define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
/* Remember to update object flag allocation in object.h */
#define REACHABLE (1u<<15)
-char *get_commit_graph_filename(const char *obj_dir)
+/* Keep track of the order in which commits are added to our list. */
+define_commit_slab(commit_pos, int);
+static struct commit_pos commit_pos = COMMIT_SLAB_INIT(1, commit_pos);
+
+static void set_commit_pos(struct repository *r, const struct object_id *oid)
+{
+ static int32_t max_pos;
+ struct commit *commit = lookup_commit(r, oid);
+
+ if (!commit)
+ return; /* should never happen, but be lenient */
+
+ *commit_pos_at(&commit_pos, commit) = max_pos++;
+}
+
+static int commit_pos_cmp(const void *va, const void *vb)
+{
+ const struct commit *a = *(const struct commit **)va;
+ const struct commit *b = *(const struct commit **)vb;
+ return commit_pos_at(&commit_pos, a) -
+ commit_pos_at(&commit_pos, b);
+}
+
+static int commit_gen_cmp(const void *va, const void *vb)
+{
+ const struct commit *a = *(const struct commit **)va;
+ const struct commit *b = *(const struct commit **)vb;
+
+ /* lower generation commits first */
+ if (a->generation < b->generation)
+ return -1;
+ else if (a->generation > b->generation)
+ return 1;
+
+ /* use date as a heuristic when generations are equal */
+ if (a->date < b->date)
+ return -1;
+ else if (a->date > b->date)
+ return 1;
+ return 0;
+}
+
+char *get_commit_graph_filename(struct object_directory *obj_dir)
{
- char *filename = xstrfmt("%s/info/commit-graph", obj_dir);
- char *normalized = xmalloc(strlen(filename) + 1);
- normalize_path_copy(normalized, filename);
- free(filename);
- return normalized;
+ return xstrfmt("%s/info/commit-graph", obj_dir->path);
}
-static char *get_split_graph_filename(const char *obj_dir,
+static char *get_split_graph_filename(struct object_directory *odb,
const char *oid_hex)
{
- char *filename = xstrfmt("%s/info/commit-graphs/graph-%s.graph",
- obj_dir,
- oid_hex);
- char *normalized = xmalloc(strlen(filename) + 1);
- normalize_path_copy(normalized, filename);
- free(filename);
- return normalized;
+ return xstrfmt("%s/info/commit-graphs/graph-%s.graph", odb->path,
+ oid_hex);
}
-static char *get_chain_filename(const char *obj_dir)
+static char *get_chain_filename(struct object_directory *odb)
{
- return xstrfmt("%s/info/commit-graphs/commit-graph-chain", obj_dir);
+ return xstrfmt("%s/info/commit-graphs/commit-graph-chain", odb->path);
}
static uint8_t oid_version(void)
return 1;
}
-struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st)
+struct commit_graph *load_commit_graph_one_fd_st(int fd, struct stat *st,
+ struct object_directory *odb)
{
void *graph_map;
size_t graph_size;
graph_map = xmmap(NULL, graph_size, PROT_READ, MAP_PRIVATE, fd, 0);
ret = parse_commit_graph(graph_map, fd, graph_size);
- if (!ret) {
+ if (ret)
+ ret->odb = odb;
+ else {
munmap(graph_map, graph_size);
close(fd);
}
chunk_repeated = 1;
else
graph->chunk_base_graphs = data + chunk_offset;
+ break;
+
+ case GRAPH_CHUNKID_BLOOMINDEXES:
+ if (graph->chunk_bloom_indexes)
+ chunk_repeated = 1;
+ else
+ graph->chunk_bloom_indexes = data + chunk_offset;
+ break;
+
+ case GRAPH_CHUNKID_BLOOMDATA:
+ if (graph->chunk_bloom_data)
+ chunk_repeated = 1;
+ else {
+ uint32_t hash_version;
+ graph->chunk_bloom_data = data + chunk_offset;
+ hash_version = get_be32(data + chunk_offset);
+
+ if (hash_version != 1)
+ break;
+
+ graph->bloom_filter_settings = xmalloc(sizeof(struct bloom_filter_settings));
+ graph->bloom_filter_settings->hash_version = hash_version;
+ graph->bloom_filter_settings->num_hashes = get_be32(data + chunk_offset + 4);
+ graph->bloom_filter_settings->bits_per_entry = get_be32(data + chunk_offset + 8);
+ }
+ break;
}
if (chunk_repeated) {
last_chunk_offset = chunk_offset;
}
+ if (graph->chunk_bloom_indexes && graph->chunk_bloom_data) {
+ init_bloom_filters();
+ } else {
+ /* We need both the bloom chunks to exist together. Else ignore the data */
+ graph->chunk_bloom_indexes = NULL;
+ graph->chunk_bloom_data = NULL;
+ graph->bloom_filter_settings = NULL;
+ }
+
hashcpy(graph->oid.hash, graph->data + graph->data_len - graph->hash_len);
if (verify_commit_graph_lite(graph)) {
return graph;
}
-static struct commit_graph *load_commit_graph_one(const char *graph_file)
+static struct commit_graph *load_commit_graph_one(const char *graph_file,
+ struct object_directory *odb)
{
struct stat st;
if (!open_ok)
return NULL;
- g = load_commit_graph_one_fd_st(fd, &st);
+ g = load_commit_graph_one_fd_st(fd, &st, odb);
if (g)
g->filename = xstrdup(graph_file);
return g;
}
-static struct commit_graph *load_commit_graph_v1(struct repository *r, const char *obj_dir)
+static struct commit_graph *load_commit_graph_v1(struct repository *r,
+ struct object_directory *odb)
{
- char *graph_name = get_commit_graph_filename(obj_dir);
- struct commit_graph *g = load_commit_graph_one(graph_name);
+ char *graph_name = get_commit_graph_filename(odb);
+ struct commit_graph *g = load_commit_graph_one(graph_name, odb);
free(graph_name);
- if (g)
- g->obj_dir = obj_dir;
-
return g;
}
return 1;
}
-static struct commit_graph *load_commit_graph_chain(struct repository *r, const char *obj_dir)
+static struct commit_graph *load_commit_graph_chain(struct repository *r,
+ struct object_directory *odb)
{
struct commit_graph *graph_chain = NULL;
struct strbuf line = STRBUF_INIT;
struct stat st;
struct object_id *oids;
int i = 0, valid = 1, count;
- char *chain_name = get_chain_filename(obj_dir);
+ char *chain_name = get_chain_filename(odb);
FILE *fp;
int stat_res;
valid = 0;
for (odb = r->objects->odb; odb; odb = odb->next) {
- char *graph_name = get_split_graph_filename(odb->path, line.buf);
- struct commit_graph *g = load_commit_graph_one(graph_name);
+ char *graph_name = get_split_graph_filename(odb, line.buf);
+ struct commit_graph *g = load_commit_graph_one(graph_name, odb);
free(graph_name);
if (g) {
- g->obj_dir = odb->path;
-
if (add_graph_to_chain(g, graph_chain, oids, i)) {
graph_chain = g;
valid = 1;
return graph_chain;
}
-struct commit_graph *read_commit_graph_one(struct repository *r, const char *obj_dir)
+struct commit_graph *read_commit_graph_one(struct repository *r,
+ struct object_directory *odb)
{
- struct commit_graph *g = load_commit_graph_v1(r, obj_dir);
+ struct commit_graph *g = load_commit_graph_v1(r, odb);
if (!g)
- g = load_commit_graph_chain(r, obj_dir);
+ g = load_commit_graph_chain(r, odb);
return g;
}
-static void prepare_commit_graph_one(struct repository *r, const char *obj_dir)
+static void prepare_commit_graph_one(struct repository *r,
+ struct object_directory *odb)
{
if (r->objects->commit_graph)
return;
- r->objects->commit_graph = read_commit_graph_one(r, obj_dir);
+ r->objects->commit_graph = read_commit_graph_one(r, odb);
}
/*
for (odb = r->objects->odb;
!r->objects->commit_graph && odb;
odb = odb->next)
- prepare_commit_graph_one(r, odb->path);
+ prepare_commit_graph_one(r, odb);
return !!r->objects->commit_graph;
}
struct write_commit_graph_context {
struct repository *r;
- char *obj_dir;
+ struct object_directory *odb;
char *graph_name;
struct packed_oid_list oids;
struct packed_commit_list commits;
unsigned append:1,
report_progress:1,
split:1,
- check_oids:1;
+ check_oids:1,
+ changed_paths:1,
+ order_by_pack:1;
const struct split_commit_graph_opts *split_opts;
+ size_t total_bloom_filter_data_size;
};
static void write_graph_chunk_fanout(struct hashfile *f,
}
}
+static void write_graph_chunk_bloom_indexes(struct hashfile *f,
+ struct write_commit_graph_context *ctx)
+{
+ struct commit **list = ctx->commits.list;
+ struct commit **last = ctx->commits.list + ctx->commits.nr;
+ uint32_t cur_pos = 0;
+ struct progress *progress = NULL;
+ int i = 0;
+
+ if (ctx->report_progress)
+ progress = start_delayed_progress(
+ _("Writing changed paths Bloom filters index"),
+ ctx->commits.nr);
+
+ while (list < last) {
+ struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
+ cur_pos += filter->len;
+ display_progress(progress, ++i);
+ hashwrite_be32(f, cur_pos);
+ list++;
+ }
+
+ stop_progress(&progress);
+}
+
+static void write_graph_chunk_bloom_data(struct hashfile *f,
+ struct write_commit_graph_context *ctx,
+ const struct bloom_filter_settings *settings)
+{
+ struct commit **list = ctx->commits.list;
+ struct commit **last = ctx->commits.list + ctx->commits.nr;
+ struct progress *progress = NULL;
+ int i = 0;
+
+ if (ctx->report_progress)
+ progress = start_delayed_progress(
+ _("Writing changed paths Bloom filters data"),
+ ctx->commits.nr);
+
+ hashwrite_be32(f, settings->hash_version);
+ hashwrite_be32(f, settings->num_hashes);
+ hashwrite_be32(f, settings->bits_per_entry);
+
+ while (list < last) {
+ struct bloom_filter *filter = get_bloom_filter(ctx->r, *list, 0);
+ display_progress(progress, ++i);
+ hashwrite(f, filter->data, filter->len * sizeof(unsigned char));
+ list++;
+ }
+
+ stop_progress(&progress);
+}
+
static int oid_compare(const void *_a, const void *_b)
{
const struct object_id *a = (const struct object_id *)_a;
oidcpy(&(ctx->oids.list[ctx->oids.nr]), oid);
ctx->oids.nr++;
+ set_commit_pos(ctx->r, oid);
+
return 0;
}
stop_progress(&ctx->progress);
}
+static void compute_bloom_filters(struct write_commit_graph_context *ctx)
+{
+ int i;
+ struct progress *progress = NULL;
+ struct commit **sorted_commits;
+
+ init_bloom_filters();
+
+ if (ctx->report_progress)
+ progress = start_delayed_progress(
+ _("Computing commit changed paths Bloom filters"),
+ ctx->commits.nr);
+
+ ALLOC_ARRAY(sorted_commits, ctx->commits.nr);
+ COPY_ARRAY(sorted_commits, ctx->commits.list, ctx->commits.nr);
+
+ if (ctx->order_by_pack)
+ QSORT(sorted_commits, ctx->commits.nr, commit_pos_cmp);
+ else
+ QSORT(sorted_commits, ctx->commits.nr, commit_gen_cmp);
+
+ for (i = 0; i < ctx->commits.nr; i++) {
+ struct commit *c = sorted_commits[i];
+ struct bloom_filter *filter = get_bloom_filter(ctx->r, c, 1);
+ ctx->total_bloom_filter_data_size += sizeof(unsigned char) * filter->len;
+ display_progress(progress, i + 1);
+ }
+
+ free(sorted_commits);
+ stop_progress(&progress);
+}
+
static int add_ref_to_list(const char *refname,
const struct object_id *oid,
int flags, void *cb_data)
return 0;
}
-int write_commit_graph_reachable(const char *obj_dir,
+int write_commit_graph_reachable(struct object_directory *odb,
enum commit_graph_write_flags flags,
const struct split_commit_graph_opts *split_opts)
{
int result;
for_each_ref(add_ref_to_list, &list);
- result = write_commit_graph(obj_dir, NULL, &list,
+ result = write_commit_graph(odb, NULL, &list,
flags, split_opts);
string_list_clear(&list, 0);
struct strbuf packname = STRBUF_INIT;
int dirlen;
- strbuf_addf(&packname, "%s/pack/", ctx->obj_dir);
+ strbuf_addf(&packname, "%s/pack/", ctx->odb->path);
dirlen = packname.len;
if (ctx->report_progress) {
strbuf_addf(&progress_title,
int fd;
struct hashfile *f;
struct lock_file lk = LOCK_INIT;
- uint32_t chunk_ids[6];
- uint64_t chunk_offsets[6];
+ uint32_t chunk_ids[MAX_NUM_CHUNKS + 1];
+ uint64_t chunk_offsets[MAX_NUM_CHUNKS + 1];
const unsigned hashsz = the_hash_algo->rawsz;
struct strbuf progress_title = STRBUF_INIT;
int num_chunks = 3;
struct object_id file_hash;
+ const struct bloom_filter_settings bloom_settings = DEFAULT_BLOOM_FILTER_SETTINGS;
if (ctx->split) {
struct strbuf tmp_file = STRBUF_INIT;
strbuf_addf(&tmp_file,
"%s/info/commit-graphs/tmp_graph_XXXXXX",
- ctx->obj_dir);
+ ctx->odb->path);
ctx->graph_name = strbuf_detach(&tmp_file, NULL);
} else {
- ctx->graph_name = get_commit_graph_filename(ctx->obj_dir);
+ ctx->graph_name = get_commit_graph_filename(ctx->odb);
}
if (safe_create_leading_directories(ctx->graph_name)) {
}
if (ctx->split) {
- char *lock_name = get_chain_filename(ctx->obj_dir);
+ char *lock_name = get_chain_filename(ctx->odb);
hold_lock_file_for_update(&lk, lock_name, LOCK_DIE_ON_ERROR);
chunk_ids[num_chunks] = GRAPH_CHUNKID_EXTRAEDGES;
num_chunks++;
}
+ if (ctx->changed_paths) {
+ chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMINDEXES;
+ num_chunks++;
+ chunk_ids[num_chunks] = GRAPH_CHUNKID_BLOOMDATA;
+ num_chunks++;
+ }
if (ctx->num_commit_graphs_after > 1) {
chunk_ids[num_chunks] = GRAPH_CHUNKID_BASE;
num_chunks++;
4 * ctx->num_extra_edges;
num_chunks++;
}
+ if (ctx->changed_paths) {
+ chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
+ sizeof(uint32_t) * ctx->commits.nr;
+ num_chunks++;
+
+ chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
+ sizeof(uint32_t) * 3 + ctx->total_bloom_filter_data_size;
+ num_chunks++;
+ }
if (ctx->num_commit_graphs_after > 1) {
chunk_offsets[num_chunks + 1] = chunk_offsets[num_chunks] +
hashsz * (ctx->num_commit_graphs_after - 1);
write_graph_chunk_data(f, hashsz, ctx);
if (ctx->num_extra_edges)
write_graph_chunk_extra_edges(f, ctx);
+ if (ctx->changed_paths) {
+ write_graph_chunk_bloom_indexes(f, ctx);
+ write_graph_chunk_bloom_data(f, ctx, &bloom_settings);
+ }
if (ctx->num_commit_graphs_after > 1 &&
write_graph_chunk_base(f, ctx)) {
return -1;
if (ctx->split && ctx->base_graph_name && ctx->num_commit_graphs_after > 1) {
char *new_base_hash = xstrdup(oid_to_hex(&ctx->new_base_graph->oid));
- char *new_base_name = get_split_graph_filename(ctx->new_base_graph->obj_dir, new_base_hash);
+ char *new_base_name = get_split_graph_filename(ctx->new_base_graph->odb, new_base_hash);
free(ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 2]);
free(ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 2]);
}
}
} else {
- char *graph_name = get_commit_graph_filename(ctx->obj_dir);
+ char *graph_name = get_commit_graph_filename(ctx->odb);
unlink(graph_name);
}
ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1] = xstrdup(oid_to_hex(&file_hash));
- final_graph_name = get_split_graph_filename(ctx->obj_dir,
+ final_graph_name = get_split_graph_filename(ctx->odb,
ctx->commit_graph_hash_after[ctx->num_commit_graphs_after - 1]);
ctx->commit_graph_filenames_after[ctx->num_commit_graphs_after - 1] = final_graph_name;
while (g && (g->num_commits <= size_mult * num_commits ||
(max_commits && num_commits > max_commits))) {
- if (strcmp(g->obj_dir, ctx->obj_dir))
+ if (g->odb != ctx->odb)
break;
num_commits += g->num_commits;
ctx->new_base_graph = g;
if (ctx->num_commit_graphs_after == 2) {
- char *old_graph_name = get_commit_graph_filename(g->obj_dir);
+ char *old_graph_name = get_commit_graph_filename(g->odb);
if (!strcmp(g->filename, old_graph_name) &&
- strcmp(g->obj_dir, ctx->obj_dir)) {
+ g->odb != ctx->odb) {
ctx->num_commit_graphs_after = 1;
ctx->new_base_graph = NULL;
}
{
struct commit_graph *g = ctx->r->objects->commit_graph;
uint32_t current_graph_number = ctx->num_commit_graphs_before;
- struct strbuf progress_title = STRBUF_INIT;
while (g && current_graph_number >= ctx->num_commit_graphs_after) {
current_graph_number--;
- if (ctx->report_progress) {
- strbuf_addstr(&progress_title, _("Merging commit-graph"));
- ctx->progress = start_delayed_progress(progress_title.buf, 0);
- }
+ if (ctx->report_progress)
+ ctx->progress = start_delayed_progress(_("Merging commit-graph"), 0);
merge_commit_graph(ctx, g);
stop_progress(&ctx->progress);
- strbuf_release(&progress_title);
g = g->base_graph;
}
if (ctx->split_opts && ctx->split_opts->expire_time)
expire_time -= ctx->split_opts->expire_time;
if (!ctx->split) {
- char *chain_file_name = get_chain_filename(ctx->obj_dir);
+ char *chain_file_name = get_chain_filename(ctx->odb);
unlink(chain_file_name);
free(chain_file_name);
ctx->num_commit_graphs_after = 0;
}
- strbuf_addstr(&path, ctx->obj_dir);
+ strbuf_addstr(&path, ctx->odb->path);
strbuf_addstr(&path, "/info/commit-graphs");
dir = opendir(path.buf);
strbuf_release(&path);
}
-int write_commit_graph(const char *obj_dir,
+int write_commit_graph(struct object_directory *odb,
struct string_list *pack_indexes,
struct string_list *commit_hex,
enum commit_graph_write_flags flags,
{
struct write_commit_graph_context *ctx;
uint32_t i, count_distinct = 0;
- size_t len;
int res = 0;
if (!commit_graph_compatible(the_repository))
ctx = xcalloc(1, sizeof(struct write_commit_graph_context));
ctx->r = the_repository;
-
- /* normalize object dir with no trailing slash */
- ctx->obj_dir = xmallocz(strlen(obj_dir) + 1);
- normalize_path_copy(ctx->obj_dir, obj_dir);
- len = strlen(ctx->obj_dir);
- if (len && ctx->obj_dir[len - 1] == '/')
- ctx->obj_dir[len - 1] = 0;
-
+ ctx->odb = odb;
ctx->append = flags & COMMIT_GRAPH_WRITE_APPEND ? 1 : 0;
ctx->report_progress = flags & COMMIT_GRAPH_WRITE_PROGRESS ? 1 : 0;
ctx->split = flags & COMMIT_GRAPH_WRITE_SPLIT ? 1 : 0;
ctx->check_oids = flags & COMMIT_GRAPH_WRITE_CHECK_OIDS ? 1 : 0;
ctx->split_opts = split_opts;
+ ctx->changed_paths = flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS ? 1 : 0;
+ ctx->total_bloom_filter_data_size = 0;
if (ctx->split) {
struct commit_graph *g;
ctx->oids.alloc = split_opts->max_commits;
if (ctx->append) {
- prepare_commit_graph_one(ctx->r, ctx->obj_dir);
+ prepare_commit_graph_one(ctx->r, ctx->odb);
if (ctx->r->objects->commit_graph)
ctx->oids.alloc += ctx->r->objects->commit_graph->num_commits;
}
}
if (pack_indexes) {
+ ctx->order_by_pack = 1;
if ((res = fill_oids_from_packs(ctx, pack_indexes)))
goto cleanup;
}
goto cleanup;
}
- if (!pack_indexes && !commit_hex)
+ if (!pack_indexes && !commit_hex) {
+ ctx->order_by_pack = 1;
fill_oids_from_all_packs(ctx);
+ }
close_reachable(ctx);
compute_generation_numbers(ctx);
+ if (ctx->changed_paths)
+ compute_bloom_filters(ctx);
+
res = write_commit_graph_file(ctx);
if (ctx->split)
free(ctx->graph_name);
free(ctx->commits.list);
free(ctx->oids.list);
- free(ctx->obj_dir);
if (ctx->commit_graph_filenames_after) {
for (i = 0; i < ctx->num_commit_graphs_after; i++) {
close(g->graph_fd);
}
free(g->filename);
+ free(g->bloom_filter_settings);
free(g);
}
projects / thirdparty / git.git / blobdiff