#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 struct bitmap_index *bitmap_git;
+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;
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),
if (!check)
check = attr_check_initl("delta", NULL);
- if (git_check_attr(&the_index, path, check))
- return 0;
+ git_check_attr(&the_index, path, check);
if (ATTR_FALSE(check->items[0].value))
return 1;
return 0;
*/
for (neigh = 0; neigh < 8; neigh++) {
ent = pbase_tree_cache[my_ix];
- if (ent && !oidcmp(&ent->oid, oid)) {
+ if (ent && oideq(&ent->oid, oid)) {
ent->ref++;
return ent;
}
return;
for (it = pbase_tree; it; it = it->next) {
- if (!oidcmp(&it->pcache.oid, &tree_oid)) {
+ if (oideq(&it->pcache.oid, &tree_oid)) {
free(data);
return;
}
done_pbase_paths_num = done_pbase_paths_alloc = 0;
}
+/*
+ * Return 1 iff the object specified by "delta" can be sent
+ * literally as a delta against the base in "base_sha1". If
+ * so, then *base_out will point to the entry in our packing
+ * list, or NULL if we must use the external-base list.
+ *
+ * Depth value does not matter - find_deltas() will
+ * never consider reused delta as the base object to
+ * deltify other objects against, in order to avoid
+ * circular deltas.
+ */
+static int can_reuse_delta(const unsigned char *base_sha1,
+ struct object_entry *delta,
+ struct object_entry **base_out)
+{
+ struct object_entry *base;
+
+ if (!base_sha1)
+ return 0;
+
+ /*
+ * First see if we're already sending the base (or it's explicitly in
+ * our "excluded" list).
+ */
+ base = packlist_find(&to_pack, base_sha1, NULL);
+ if (base) {
+ if (!in_same_island(&delta->idx.oid, &base->idx.oid))
+ return 0;
+ *base_out = base;
+ return 1;
+ }
+
+ /*
+ * Otherwise, reachability bitmaps may tell us if the receiver has it,
+ * even if it was buried too deep in history to make it into the
+ * packing list.
+ */
+ if (thin && bitmap_has_sha1_in_uninteresting(bitmap_git, base_sha1)) {
+ if (use_delta_islands) {
+ struct object_id base_oid;
+ hashcpy(base_oid.hash, base_sha1);
+ if (!in_same_island(&delta->idx.oid, &base_oid))
+ return 0;
+ }
+ *base_out = NULL;
+ return 1;
+ }
+
+ return 0;
+}
+
static void check_object(struct object_entry *entry)
{
unsigned long canonical_size;
break;
}
- if (base_ref && (
- (base_entry = packlist_find(&to_pack, base_ref, NULL)) ||
- (thin &&
- bitmap_has_sha1_in_uninteresting(bitmap_git, base_ref)))) {
- /*
- * If base_ref was set above that means we wish to
- * reuse delta data, and either we found that object in
- * the list of objects we want to pack, or it's one we
- * know the receiver has.
- *
- * Depth value does not matter - find_deltas() will
- * never consider reused delta as the base object to
- * deltify other objects against, in order to avoid
- * circular deltas.
- */
+ if (can_reuse_delta(base_ref, entry, &base_entry)) {
oe_set_type(entry, entry->in_pack_type);
SET_SIZE(entry, in_pack_size); /* delta size */
SET_DELTA_SIZE(entry, in_pack_size);
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)
return 0;
}
-#ifndef NO_PTHREADS
-
/* Protect access to object database */
static pthread_mutex_t read_mutex;
#define read_lock() pthread_mutex_lock(&read_mutex)
* ahead in the list because they can be stolen and would need
* progress_mutex for protection.
*/
-#else
-
-#define read_lock() (void)0
-#define read_unlock() (void)0
-#define cache_lock() (void)0
-#define cache_unlock() (void)0
-#define progress_lock() (void)0
-#define progress_unlock() (void)0
-
-#endif
/*
* Return the size of the object without doing any delta
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();
die(_("object %s cannot be read"),
oid_to_hex(&trg_entry->idx.oid));
if (sz != trg_size)
- die(_("object %s inconsistent object length (%lu vs %lu)"),
- oid_to_hex(&trg_entry->idx.oid), sz,
- trg_size);
+ die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
+ oid_to_hex(&trg_entry->idx.oid), (uintmax_t)sz,
+ (uintmax_t)trg_size);
*mem_usage += sz;
}
if (!src->data) {
oid_to_hex(&src_entry->idx.oid));
}
if (sz != src_size)
- die(_("object %s inconsistent object length (%lu vs %lu)"),
- oid_to_hex(&src_entry->idx.oid), sz,
- src_size);
+ die(_("object %s inconsistent object length (%"PRIuMAX" vs %"PRIuMAX")"),
+ oid_to_hex(&src_entry->idx.oid), (uintmax_t)sz,
+ (uintmax_t)src_size);
*mem_usage += sz;
}
if (!src->index) {
free(array);
}
-#ifndef NO_PTHREADS
-
static void try_to_free_from_threads(size_t size)
{
read_lock();
pthread_mutex_init(&cache_mutex, NULL);
pthread_mutex_init(&progress_mutex, NULL);
pthread_cond_init(&progress_cond, NULL);
- pthread_mutex_init(&to_pack.lock, NULL);
old_try_to_free_routine = set_try_to_free_routine(try_to_free_from_threads);
}
free(p);
}
-#else
-#define ll_find_deltas(l, s, w, d, p) find_deltas(l, &s, w, d, p)
-#endif
-
static void add_tag_chain(const struct object_id *oid)
{
struct tag *tag;
uint32_t i, nr_deltas;
unsigned n;
+ if (use_delta_islands)
+ resolve_tree_islands(progress, &to_pack);
+
get_object_details();
/*
if (delta_search_threads < 0)
die(_("invalid number of threads specified (%d)"),
delta_search_threads);
-#ifdef NO_PTHREADS
- if (delta_search_threads != 1) {
+ if (!HAVE_THREADS && delta_search_threads != 1) {
warning(_("no threads support, ignoring %s"), k);
delta_search_threads = 0;
}
-#endif
return 0;
}
if (!strcmp(k, "pack.indexversion")) {
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;
+ struct object_entry *ent;
+
+ /* the empty string is a root tree, which is depth 0 */
+ depth = *name ? 1 : 0;
+ 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)
struct rev_info revs;
char line[1000];
int flags = 0;
+ int save_warning;
- init_revisions(&revs, NULL);
+ repo_init_revisions(the_repository, &revs, NULL);
save_commit_buffer = 0;
+ revs.allow_exclude_promisor_objects_opt = 1;
setup_revisions(ac, av, &revs, NULL);
/* make sure shallows are read */
is_repository_shallow(the_repository);
+ save_warning = warn_on_object_refname_ambiguity;
+ warn_on_object_refname_ambiguity = 0;
+
while (fgets(line, sizeof(line), stdin) != NULL) {
int len = strlen(line);
if (len && line[len - 1] == '\n')
die(_("bad revision '%s'"), line);
}
+ warn_on_object_refname_ambiguity = save_warning;
+
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);
{
char *c;
const char *val = arg;
+
+ BUG_ON_OPT_NEG(unset);
+
pack_idx_opts.version = strtoul(val, &c, 10);
if (pack_idx_opts.version > 2)
die(_("unsupported index version %s"), val);
N_("similar to --all-progress when progress meter is shown")),
{ OPTION_CALLBACK, 0, "index-version", NULL, N_("<version>[,<offset>]"),
N_("write the pack index file in the specified idx format version"),
- 0, option_parse_index_version },
+ PARSE_OPT_NONEG, option_parse_index_version },
OPT_MAGNITUDE(0, "max-pack-size", &pack_size_limit,
N_("maximum size of each output pack file")),
OPT_BOOL(0, "local", &local,
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(),
};
if (!delta_search_threads) /* --threads=0 means autodetect */
delta_search_threads = online_cpus();
-#ifdef NO_PTHREADS
- if (delta_search_threads != 1)
+ if (!HAVE_THREADS && delta_search_threads != 1)
warning(_("no threads support, ignoring --threads"));
-#endif
if (!pack_to_stdout && !pack_size_limit)
pack_size_limit = pack_size_limit_cfg;
if (pack_to_stdout && pack_size_limit)
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;