From: Junio C Hamano Date: Mon, 17 Sep 2018 20:53:55 +0000 (-0700) Subject: Merge branch 'cc/delta-islands' X-Git-Tag: v2.20.0-rc0~241 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/f3504ea3dd Merge branch 'cc/delta-islands' Lift code from GitHub to restrict delta computation so that an object that exists in one fork is not made into a delta against another object that does not appear in the same forked repository. * cc/delta-islands: pack-objects: move 'layer' into 'struct packing_data' pack-objects: move tree_depth into 'struct packing_data' t5320: tests for delta islands repack: add delta-islands support pack-objects: add delta-islands support pack-objects: refactor code into compute_layer_order() Add delta-islands.{c,h} --- f3504ea3dd21b0a6d38bcd369efa0663cdc05416 diff --cc builtin/pack-objects.c index f434e1fb0c,d5d91eeed5..425bdc8ac5 --- a/builtin/pack-objects.c +++ b/builtin/pack-objects.c @@@ -61,7 -60,7 +62,8 @@@ static struct packing_data to_pack 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; @@@ -752,13 -714,56 +723,57 @@@ static void compute_layer_order(struct * 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(_("ordered %u objects, expected %"PRIu32), + wo_end, to_pack.nr_objects); return wo; } @@@ -1541,15 -1519,12 +1556,16 @@@ static void check_object(struct object_ 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)) || + (thin && - bitmap_has_sha1_in_uninteresting(bitmap_git, base_ref)))) { ++ bitmap_has_sha1_in_uninteresting(bitmap_git, base_ref))) && + 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 - * in the list of objects we want to pack. Goodie! + * 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 @@@ -3064,8 -3046,11 +3107,11 @@@ static void get_object_list(int ac, con 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"); + die(_("revision walk setup failed")); mark_edges_uninteresting(&revs, show_edge); if (!fn_show_object) diff --cc builtin/repack.c index 42be88e86c,5ab9ee69e4..c6a7943d5c --- a/builtin/repack.c +++ b/builtin/repack.c @@@ -361,8 -258,24 +368,10 @@@ int cmd_repack(int argc, const char **a argv_array_push(&cmd.args, "--indexed-objects"); if (repository_format_partial_clone) argv_array_push(&cmd.args, "--exclude-promisor-objects"); - if (window) - argv_array_pushf(&cmd.args, "--window=%s", window); - if (window_memory) - argv_array_pushf(&cmd.args, "--window-memory=%s", window_memory); - if (depth) - argv_array_pushf(&cmd.args, "--depth=%s", depth); - if (threads) - argv_array_pushf(&cmd.args, "--threads=%s", threads); - if (max_pack_size) - argv_array_pushf(&cmd.args, "--max-pack-size=%s", max_pack_size); - if (no_reuse_delta) - argv_array_pushf(&cmd.args, "--no-reuse-delta"); - if (no_reuse_object) - argv_array_pushf(&cmd.args, "--no-reuse-object"); if (write_bitmaps) argv_array_push(&cmd.args, "--write-bitmap-index"); + if (use_delta_islands) + argv_array_push(&cmd.args, "--delta-islands"); if (pack_everything & ALL_INTO_ONE) { get_non_kept_pack_filenames(&existing_packs, &keep_pack_list); diff --cc pack-objects.c index 3462858772,98389460c2..7f7b7dddf6 --- a/pack-objects.c +++ b/pack-objects.c @@@ -162,8 -160,12 +162,14 @@@ struct object_entry *packlist_alloc(str if (!pdata->in_pack_by_idx) REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc); + if (pdata->delta_size) + REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc); + + if (pdata->tree_depth) + REALLOC_ARRAY(pdata->tree_depth, pdata->nr_alloc); + + if (pdata->layer) + REALLOC_ARRAY(pdata->layer, pdata->nr_alloc); } new_entry = pdata->objects + pdata->nr_objects++; @@@ -179,24 -181,11 +185,30 @@@ if (pdata->in_pack) pdata->in_pack[pdata->nr_objects - 1] = NULL; + if (pdata->tree_depth) + pdata->tree_depth[pdata->nr_objects - 1] = 0; + + if (pdata->layer) + pdata->layer[pdata->nr_objects - 1] = 0; + return new_entry; } + +void oe_set_delta_ext(struct packing_data *pdata, + struct object_entry *delta, + const unsigned char *sha1) +{ + struct object_entry *base; + + ALLOC_GROW(pdata->ext_bases, pdata->nr_ext + 1, pdata->alloc_ext); + base = &pdata->ext_bases[pdata->nr_ext++]; + memset(base, 0, sizeof(*base)); + hashcpy(base->idx.oid.hash, sha1); + + /* These flags mark that we are not part of the actual pack output. */ + base->preferred_base = 1; + base->filled = 1; + + delta->ext_base = 1; + delta->delta_idx = base - pdata->ext_bases + 1; +} diff --cc pack-objects.h index b0c1f137c6,ad3c208764..2ca39cfcfe --- a/pack-objects.h +++ b/pack-objects.h @@@ -100,9 -97,10 +100,10 @@@ struct object_entry unsigned in_pack_idx:OE_IN_PACK_BITS; /* already in pack */ unsigned z_delta_size:OE_Z_DELTA_BITS; unsigned type_valid:1; - unsigned type_:TYPE_BITS; unsigned no_try_delta:1; + unsigned type_:TYPE_BITS; unsigned in_pack_type:TYPE_BITS; /* could be delta */ + unsigned preferred_base:1; /* * we do not pack this, but is available * to be used as the base object to delta @@@ -144,20 -141,11 +145,24 @@@ struct packing_data struct packed_git **in_pack_by_idx; struct packed_git **in_pack; +#ifndef NO_PTHREADS + pthread_mutex_t lock; +#endif + + /* + * This list contains entries for bases which we know the other side + * has (e.g., via reachability bitmaps), but which aren't in our + * "objects" list. + */ + struct object_entry *ext_bases; + uint32_t nr_ext, alloc_ext; + uintmax_t oe_size_limit; + uintmax_t oe_delta_size_limit; + + /* delta islands */ + unsigned int *tree_depth; + unsigned char *layer; }; void prepare_packing_data(struct packing_data *pdata); @@@ -386,18 -344,45 +391,52 @@@ static inline void oe_set_delta_size(st struct object_entry *e, unsigned long size) { - e->delta_size_ = size; - e->delta_size_valid = e->delta_size_ == size; - if (!e->delta_size_valid && size != oe_size(pack, e)) - BUG("this can only happen in check_object() " - "where delta size is the same as entry size"); + if (size < pack->oe_delta_size_limit) { + e->delta_size_ = size; + e->delta_size_valid = 1; + } else { + packing_data_lock(pack); + if (!pack->delta_size) + ALLOC_ARRAY(pack->delta_size, pack->nr_alloc); + packing_data_unlock(pack); + + pack->delta_size[e - pack->objects] = size; + e->delta_size_valid = 0; + } } + static inline unsigned int oe_tree_depth(struct packing_data *pack, + struct object_entry *e) + { + if (!pack->tree_depth) + return 0; + return pack->tree_depth[e - pack->objects]; + } + + static inline void oe_set_tree_depth(struct packing_data *pack, + struct object_entry *e, + unsigned int tree_depth) + { + if (!pack->tree_depth) + ALLOC_ARRAY(pack->tree_depth, pack->nr_objects); + pack->tree_depth[e - pack->objects] = tree_depth; + } + + static inline unsigned char oe_layer(struct packing_data *pack, + struct object_entry *e) + { + if (!pack->layer) + return 0; + return pack->layer[e - pack->objects]; + } + + static inline void oe_set_layer(struct packing_data *pack, + struct object_entry *e, + unsigned char layer) + { + if (!pack->layer) + ALLOC_ARRAY(pack->layer, pack->nr_objects); + pack->layer[e - pack->objects] = layer; + } + #endif