#include "streaming.h"
#include "thread-utils.h"
#include "pack-bitmap.h"
+#include "delta-islands.h"
#include "reachable.h"
#include "sha1-array.h"
#include "argv-array.h"
static struct pack_idx_entry **written_list;
static uint32_t nr_result, nr_written, nr_seen;
+static uint32_t write_layer;
static int non_empty;
static int reuse_delta = 1, reuse_object = 1;
static int exclude_promisor_objects;
+static int use_delta_islands;
+
static unsigned long delta_cache_size = 0;
static unsigned long max_delta_cache_size = DEFAULT_DELTA_CACHE_SIZE;
static unsigned long cache_max_small_delta_size = 1000;
enum object_type type;
void *buf;
struct git_istream *st = NULL;
+ const unsigned hashsz = the_hash_algo->rawsz;
if (!usable_delta) {
if (oe_type(entry) == OBJ_BLOB &&
dheader[pos] = ofs & 127;
while (ofs >>= 7)
dheader[--pos] = 128 | (--ofs & 127);
- if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {
+ if (limit && hdrlen + sizeof(dheader) - pos + datalen + hashsz >= limit) {
if (st)
close_istream(st);
free(buf);
} else if (type == OBJ_REF_DELTA) {
/*
* Deltas with a base reference contain
- * an additional 20 bytes for the base sha1.
+ * additional bytes for the base object ID.
*/
- if (limit && hdrlen + 20 + datalen + 20 >= limit) {
+ if (limit && hdrlen + hashsz + datalen + hashsz >= limit) {
if (st)
close_istream(st);
free(buf);
return 0;
}
hashwrite(f, header, hdrlen);
- hashwrite(f, DELTA(entry)->idx.oid.hash, 20);
- hdrlen += 20;
+ hashwrite(f, DELTA(entry)->idx.oid.hash, hashsz);
+ hdrlen += hashsz;
} else {
- if (limit && hdrlen + datalen + 20 >= limit) {
+ if (limit && hdrlen + datalen + hashsz >= limit) {
if (st)
close_istream(st);
free(buf);
unsigned char header[MAX_PACK_OBJECT_HEADER],
dheader[MAX_PACK_OBJECT_HEADER];
unsigned hdrlen;
+ const unsigned hashsz = the_hash_algo->rawsz;
unsigned long entry_size = SIZE(entry);
if (DELTA(entry))
dheader[pos] = ofs & 127;
while (ofs >>= 7)
dheader[--pos] = 128 | (--ofs & 127);
- if (limit && hdrlen + sizeof(dheader) - pos + datalen + 20 >= limit) {
+ if (limit && hdrlen + sizeof(dheader) - pos + datalen + hashsz >= limit) {
unuse_pack(&w_curs);
return 0;
}
hdrlen += sizeof(dheader) - pos;
reused_delta++;
} else if (type == OBJ_REF_DELTA) {
- if (limit && hdrlen + 20 + datalen + 20 >= limit) {
+ if (limit && hdrlen + hashsz + datalen + hashsz >= limit) {
unuse_pack(&w_curs);
return 0;
}
hashwrite(f, header, hdrlen);
- hashwrite(f, DELTA(entry)->idx.oid.hash, 20);
- hdrlen += 20;
+ hashwrite(f, DELTA(entry)->idx.oid.hash, hashsz);
+ hdrlen += hashsz;
reused_delta++;
} else {
- if (limit && hdrlen + datalen + 20 >= limit) {
+ if (limit && hdrlen + datalen + hashsz >= limit) {
unuse_pack(&w_curs);
return 0;
}
unsigned int *endp,
struct object_entry *e)
{
- if (e->filled)
+ if (e->filled || oe_layer(&to_pack, e) != write_layer)
return;
wo[(*endp)++] = e;
e->filled = 1;
add_descendants_to_write_order(wo, endp, root);
}
-static struct object_entry **compute_write_order(void)
+static void compute_layer_order(struct object_entry **wo, unsigned int *wo_end)
{
- unsigned int i, wo_end, last_untagged;
-
- struct object_entry **wo;
+ unsigned int i, last_untagged;
struct object_entry *objects = to_pack.objects;
for (i = 0; i < to_pack.nr_objects; i++) {
- objects[i].tagged = 0;
- objects[i].filled = 0;
- SET_DELTA_CHILD(&objects[i], NULL);
- SET_DELTA_SIBLING(&objects[i], NULL);
- }
-
- /*
- * Fully connect delta_child/delta_sibling network.
- * Make sure delta_sibling is sorted in the original
- * recency order.
- */
- for (i = to_pack.nr_objects; i > 0;) {
- struct object_entry *e = &objects[--i];
- if (!DELTA(e))
- continue;
- /* Mark me as the first child */
- e->delta_sibling_idx = DELTA(e)->delta_child_idx;
- SET_DELTA_CHILD(DELTA(e), e);
- }
-
- /*
- * Mark objects that are at the tip of tags.
- */
- for_each_tag_ref(mark_tagged, NULL);
-
- /*
- * Give the objects in the original recency order until
- * we see a tagged tip.
- */
- ALLOC_ARRAY(wo, to_pack.nr_objects);
- for (i = wo_end = 0; i < to_pack.nr_objects; i++) {
if (objects[i].tagged)
break;
- add_to_write_order(wo, &wo_end, &objects[i]);
+ add_to_write_order(wo, wo_end, &objects[i]);
}
last_untagged = i;
*/
for (; i < to_pack.nr_objects; i++) {
if (objects[i].tagged)
- add_to_write_order(wo, &wo_end, &objects[i]);
+ add_to_write_order(wo, wo_end, &objects[i]);
}
/*
if (oe_type(&objects[i]) != OBJ_COMMIT &&
oe_type(&objects[i]) != OBJ_TAG)
continue;
- add_to_write_order(wo, &wo_end, &objects[i]);
+ add_to_write_order(wo, wo_end, &objects[i]);
}
/*
for (i = last_untagged; i < to_pack.nr_objects; i++) {
if (oe_type(&objects[i]) != OBJ_TREE)
continue;
- add_to_write_order(wo, &wo_end, &objects[i]);
+ add_to_write_order(wo, wo_end, &objects[i]);
}
/*
* Finally all the rest in really tight order
*/
for (i = last_untagged; i < to_pack.nr_objects; i++) {
- if (!objects[i].filled)
- add_family_to_write_order(wo, &wo_end, &objects[i]);
+ if (!objects[i].filled && oe_layer(&to_pack, &objects[i]) == write_layer)
+ add_family_to_write_order(wo, wo_end, &objects[i]);
+ }
+}
+
+static struct object_entry **compute_write_order(void)
+{
+ uint32_t max_layers = 1;
+ unsigned int i, wo_end;
+
+ struct object_entry **wo;
+ struct object_entry *objects = to_pack.objects;
+
+ for (i = 0; i < to_pack.nr_objects; i++) {
+ objects[i].tagged = 0;
+ objects[i].filled = 0;
+ SET_DELTA_CHILD(&objects[i], NULL);
+ SET_DELTA_SIBLING(&objects[i], NULL);
+ }
+
+ /*
+ * Fully connect delta_child/delta_sibling network.
+ * Make sure delta_sibling is sorted in the original
+ * recency order.
+ */
+ for (i = to_pack.nr_objects; i > 0;) {
+ struct object_entry *e = &objects[--i];
+ if (!DELTA(e))
+ continue;
+ /* Mark me as the first child */
+ e->delta_sibling_idx = DELTA(e)->delta_child_idx;
+ SET_DELTA_CHILD(DELTA(e), e);
}
+ /*
+ * Mark objects that are at the tip of tags.
+ */
+ for_each_tag_ref(mark_tagged, NULL);
+
+ if (use_delta_islands)
+ max_layers = compute_pack_layers(&to_pack);
+
+ ALLOC_ARRAY(wo, to_pack.nr_objects);
+ wo_end = 0;
+
+ for (; write_layer < max_layers; ++write_layer)
+ compute_layer_order(wo, &wo_end);
+
if (wo_end != to_pack.nr_objects)
die("ordered %u objects, expected %"PRIu32, wo_end, to_pack.nr_objects);
die_errno("unable to seek in reused packfile");
if (reuse_packfile_offset < 0)
- reuse_packfile_offset = reuse_packfile->pack_size - 20;
+ reuse_packfile_offset = reuse_packfile->pack_size - the_hash_algo->rawsz;
total = to_write = reuse_packfile_offset - sizeof(struct pack_header);
int want;
struct list_head *pos;
- if (!exclude && local && has_loose_object_nonlocal(oid->hash))
+ if (!exclude && local && has_loose_object_nonlocal(oid))
return 0;
/*
if (reuse_delta && !entry->preferred_base)
base_ref = use_pack(p, &w_curs,
entry->in_pack_offset + used, NULL);
- entry->in_pack_header_size = used + 20;
+ entry->in_pack_header_size = used + the_hash_algo->rawsz;
break;
case OBJ_OFS_DELTA:
buf = use_pack(p, &w_curs,
break;
}
- if (base_ref && (base_entry = packlist_find(&to_pack, base_ref, NULL))) {
+ if (base_ref && (base_entry = packlist_find(&to_pack, base_ref, NULL)) &&
+ in_same_island(&entry->idx.oid, &base_entry->idx.oid)) {
/*
* If base_ref was set above that means we wish to
* reuse delta data, and we even found that base
* is a bug.
*/
if (cur->dfs_state != DFS_NONE)
- die("BUG: confusing delta dfs state in first pass: %d",
+ BUG("confusing delta dfs state in first pass: %d",
cur->dfs_state);
/*
if (cur->dfs_state == DFS_DONE)
break;
else if (cur->dfs_state != DFS_ACTIVE)
- die("BUG: confusing delta dfs state in second pass: %d",
+ BUG("confusing delta dfs state in second pass: %d",
cur->dfs_state);
/*
return -1;
if (a->preferred_base < b->preferred_base)
return 1;
+ if (use_delta_islands) {
+ int island_cmp = island_delta_cmp(&a->idx.oid, &b->idx.oid);
+ if (island_cmp)
+ return island_cmp;
+ }
if (a_size > b_size)
return -1;
if (a_size < b_size)
/* Now some size filtering heuristics. */
trg_size = SIZE(trg_entry);
if (!DELTA(trg_entry)) {
- max_size = trg_size/2 - 20;
+ max_size = trg_size/2 - the_hash_algo->rawsz;
ref_depth = 1;
} else {
max_size = DELTA_SIZE(trg_entry);
if (trg_size < src_size / 32)
return 0;
+ if (!in_same_island(&trg->entry->idx.oid, &src->entry->idx.oid))
+ return 0;
+
/* Load data if not already done */
if (!trg->data) {
read_lock();
if (packlist_find(&to_pack, oid->hash, NULL))
return;
- tag = lookup_tag(oid);
+ tag = lookup_tag(the_repository, oid);
while (1) {
if (!tag || parse_tag(tag) || !tag->tagged)
die("unable to pack objects reachable from tag %s",
uint32_t i, nr_deltas;
unsigned n;
+ if (use_delta_islands)
+ resolve_tree_islands(progress, &to_pack);
+
get_object_details();
/*
if (write_bitmap_index)
index_commit_for_bitmap(commit);
+
+ if (use_delta_islands)
+ propagate_island_marks(commit);
}
static void show_object(struct object *obj, const char *name, void *data)
add_preferred_base_object(name);
add_object_entry(&obj->oid, obj->type, name, 0);
obj->flags |= OBJECT_ADDED;
+
+ if (use_delta_islands) {
+ const char *p;
+ unsigned depth = 0;
+ struct object_entry *ent;
+
+ for (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))
+ depth++;
+
+ ent = packlist_find(&to_pack, obj->oid.hash, NULL);
+ if (ent && depth > oe_tree_depth(&to_pack, ent))
+ oe_set_tree_depth(&to_pack, ent, depth);
+ }
}
static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)
static int get_object_list_from_bitmap(struct rev_info *revs)
{
- if (prepare_bitmap_walk(revs) < 0)
+ struct bitmap_index *bitmap_git;
+ if (!(bitmap_git = prepare_bitmap_walk(revs)))
return -1;
if (pack_options_allow_reuse() &&
!reuse_partial_packfile_from_bitmap(
+ bitmap_git,
&reuse_packfile,
&reuse_packfile_objects,
&reuse_packfile_offset)) {
display_progress(progress_state, nr_result);
}
- traverse_bitmap_commit_list(&add_object_entry_from_bitmap);
+ traverse_bitmap_commit_list(bitmap_git, &add_object_entry_from_bitmap);
+ free_bitmap_index(bitmap_git);
return 0;
}
setup_revisions(ac, av, &revs, NULL);
/* make sure shallows are read */
- is_repository_shallow();
+ is_repository_shallow(the_repository);
while (fgets(line, sizeof(line), stdin) != NULL) {
int len = strlen(line);
struct object_id oid;
if (get_oid_hex(line + 10, &oid))
die("not an SHA-1 '%s'", line + 10);
- register_shallow(&oid);
+ register_shallow(the_repository, &oid);
use_bitmap_index = 0;
continue;
}
if (use_bitmap_index && !get_object_list_from_bitmap(&revs))
return;
+ if (use_delta_islands)
+ load_delta_islands();
+
if (prepare_revision_walk(&revs))
die("revision walk setup failed");
mark_edges_uninteresting(&revs, show_edge);
N_("do not create an empty pack output")),
OPT_BOOL(0, "revs", &use_internal_rev_list,
N_("read revision arguments from standard input")),
- { OPTION_SET_INT, 0, "unpacked", &rev_list_unpacked, NULL,
- N_("limit the objects to those that are not yet packed"),
- PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, 1 },
- { OPTION_SET_INT, 0, "all", &rev_list_all, NULL,
- N_("include objects reachable from any reference"),
- PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, 1 },
- { OPTION_SET_INT, 0, "reflog", &rev_list_reflog, NULL,
- N_("include objects referred by reflog entries"),
- PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, 1 },
- { OPTION_SET_INT, 0, "indexed-objects", &rev_list_index, NULL,
- N_("include objects referred to by the index"),
- PARSE_OPT_NOARG | PARSE_OPT_NONEG, NULL, 1 },
+ OPT_SET_INT_F(0, "unpacked", &rev_list_unpacked,
+ N_("limit the objects to those that are not yet packed"),
+ 1, PARSE_OPT_NONEG),
+ OPT_SET_INT_F(0, "all", &rev_list_all,
+ N_("include objects reachable from any reference"),
+ 1, PARSE_OPT_NONEG),
+ OPT_SET_INT_F(0, "reflog", &rev_list_reflog,
+ N_("include objects referred by reflog entries"),
+ 1, PARSE_OPT_NONEG),
+ OPT_SET_INT_F(0, "indexed-objects", &rev_list_index,
+ N_("include objects referred to by the index"),
+ 1, PARSE_OPT_NONEG),
OPT_BOOL(0, "stdout", &pack_to_stdout,
N_("output pack to stdout")),
OPT_BOOL(0, "include-tag", &include_tag,
option_parse_missing_action },
OPT_BOOL(0, "exclude-promisor-objects", &exclude_promisor_objects,
N_("do not pack objects in promisor packfiles")),
+ OPT_BOOL(0, "delta-islands", &use_delta_islands,
+ N_("respect islands during delta compression")),
OPT_END(),
};
use_bitmap_index = use_bitmap_index_default;
/* "hard" reasons not to use bitmaps; these just won't work at all */
- if (!use_internal_rev_list || (!pack_to_stdout && write_bitmap_index) || is_repository_shallow())
+ if (!use_internal_rev_list || (!pack_to_stdout && write_bitmap_index) || is_repository_shallow(the_repository))
use_bitmap_index = 0;
if (pack_to_stdout || !rev_list_all)
write_bitmap_index = 0;
+ if (use_delta_islands)
+ argv_array_push(&rp, "--topo-order");
+
if (progress && all_progress_implied)
progress = 2;