{"thread":{"id":"48935","subject":"[RFC PATCH 0/5] Add delta islands support","startedAt":"2018-07-22T05:49:00Z","lastAt":"2018-08-06T19:21:36Z","messageCount":37,"participants":["Christian Couder","Duy Nguyen","Stefan Beller","Jeff King","Junio C Hamano","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"353288","messageId":"20180722054836.28935-1-chriscool@tuxfamily.org","threadId":"48935","inReplyTo":null,"subject":"[RFC PATCH 0/5] Add delta islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-07-22T05:48:31Z","receivedAt":"2018-07-22T05:49:00Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This patch series is upstreaming work made by GitHub and available in:\n\nhttps://github.com/peff/git/commits/jk/delta-islands\n\nThe patch in the above branch has been split into 5 patches with their\nown new commit message, but no other change has been made.\n\nI kept Peff as the author and took the liberty to add his\nSigned-off-by to all the patches.\n\nThe patches look good to me except perhaps that \"pack.islandCore\" is\nnot documented. Maybe something could be added in\nDocumentation/technical/ too, or maybe improving commit messages could\nbe enough.\n\nAnyway I wanted to send this nearly \"as is\" first to get early\nfeedback about what should be done.\n\nThis patch series is also available on GitHub in:\n\nhttps://github.com/chriscool/git/commits/delta-islands\n\nJeff King (5):\n packfile: make get_delta_base() non static\n Add delta-islands.{c,h}\n pack-objects: add delta-islands support\n repack: add delta-islands support\n t: add t9930-delta-islands.sh\n\n Documentation/config.txt | 8 +\n Documentation/git-pack-objects.txt | 88 ++++++\n Documentation/git-repack.txt | 5 +\n Makefile | 1 +\n builtin/pack-objects.c | 130 +++++---\n builtin/repack.c | 9 +\n delta-islands.c | 490 +++++++++++++++++++++++++++++\n delta-islands.h | 11 +\n pack-objects.h | 4 +\n packfile.c | 10 +-\n packfile.h | 3 +\n t/t9930-delta-islands.sh | 143 +++++++++\n 12 files changed, 856 insertions(+), 46 deletions(-)\n create mode 100644 delta-islands.c\n create mode 100644 delta-islands.h\n create mode 100755 t/t9930-delta-islands.sh\n\n-- \n2.18.0.237.gffdb1dbdaa\n\n"},{"id":"353289","messageId":"20180722054836.28935-2-chriscool@tuxfamily.org","threadId":"48935","inReplyTo":"20180722054836.28935-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 1/5] packfile: make get_delta_base() non static","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-07-22T05:48:32Z","receivedAt":"2018-07-22T05:49:02Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nAs get_delta_base() will be used outside 'packfile.c' in\na following commit, let's make it non static and let's\ndeclare it in 'packfile.h'.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n packfile.c | 10 +++++-----\n packfile.h | 3 +++\n 2 files changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/packfile.c b/packfile.c\nindex 7cd45aa4b2..4646bff5ff 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1037,11 +1037,11 @@ const struct packed_git *has_packed_and_bad(const unsigned char *sha1)\n \treturn NULL;\n }\n \n-static off_t get_delta_base(struct packed_git *p,\n-\t\t\t\t struct pack_window **w_curs,\n-\t\t\t\t off_t *curpos,\n-\t\t\t\t enum object_type type,\n-\t\t\t\t off_t delta_obj_offset)\n+off_t get_delta_base(struct packed_git *p,\n+\t\t struct pack_window **w_curs,\n+\t\t off_t *curpos,\n+\t\t enum object_type type,\n+\t\t off_t delta_obj_offset)\n {\n \tunsigned char *base_info = use_pack(p, w_curs, *curpos, NULL);\n \toff_t base_offset;\ndiff --git a/packfile.h b/packfile.h\nindex cc7eaffe1b..30f0811382 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -125,6 +125,9 @@ extern void *unpack_entry(struct repository *r, struct packed_git *, off_t, enum\n extern unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\n extern unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);\n extern int unpack_object_header(struct packed_git *, struct pack_window **, off_t *, unsigned long *);\n+extern off_t get_delta_base(struct packed_git *p, struct pack_window **w_curs,\n+\t\t\t off_t *curpos, enum object_type type,\n+\t\t\t off_t delta_obj_offset);\n \n extern void release_pack_memory(size_t);\n \n-- \n2.18.0.237.gffdb1dbdaa\n\n"},{"id":"353290","messageId":"20180722054836.28935-3-chriscool@tuxfamily.org","threadId":"48935","inReplyTo":"20180722054836.28935-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-07-22T05:48:33Z","receivedAt":"2018-07-22T05:49:05Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nHosting providers that allow users to \"fork\" existing\nrepos want as much as possible those forks to use a\nsmall amount of disk space.\n\nUsing alternates to keep all the objects from all\nthe forks into a unique central repo is way to do\nthat, but it can have some drawbacks. Especially when\npacking the central repo, deltas will be created\nbetween objects from different forks.\n\nThis can make cloning or fetching a fork much slower\nand much more CPU intensive as Git might have to\ncompute new deltas for many objects to avoid sending\nobjects from a different fork.\n\nDelta islands is a way to store objects from\ndifferent forks in the same repo and packfile without\nhaving deltas between objects from different forks.\n\nThis patch implements the delta islands mechanism in\n\"delta-islands.{c,h}\", but does not yet make use of it.\n\nA few new fields are added in 'struct object_entry'\nin \"pack-objects.h\" though.\n\nThe new \"pack.island\" config variable which can be\nused to configure the different islands is described\na bit in \"Documentation/config.txt\", but the real\ndocumentation will follow in a patch that actually\nuses delta islands in \"builtin/pack-objects.c\".\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Documentation/config.txt | 4 +\n Makefile | 1 +\n delta-islands.c | 490 +++++++++++++++++++++++++++++++++++++++\n delta-islands.h | 11 +\n pack-objects.h | 4 +\n 5 files changed, 510 insertions(+)\n create mode 100644 delta-islands.c\n create mode 100644 delta-islands.h\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex a32172a43c..f682e92a1a 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -2542,6 +2542,10 @@ Note that changing the compression level will not automatically recompress\n all existing objects. You can force recompression by passing the -F option\n to linkgit:git-repack[1].\n \n+pack.island::\n+\tA regular expression configuring a set of delta islands. See\n+\t\"DELTA ISLANDS\" in linkgit:git-pack-objects[1] for details.\n+\n pack.deltaCacheSize::\n \tThe maximum memory in bytes used for caching deltas in\n \tlinkgit:git-pack-objects[1] before writing them out to a pack.\ndiff --git a/Makefile b/Makefile\nindex 08e5c54549..2804298977 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -840,6 +840,7 @@ LIB_OBJS += csum-file.o\n LIB_OBJS += ctype.o\n LIB_OBJS += date.o\n LIB_OBJS += decorate.o\n+LIB_OBJS += delta-islands.o\n LIB_OBJS += diffcore-break.o\n LIB_OBJS += diffcore-delta.o\n LIB_OBJS += diffcore-order.o\ndiff --git a/delta-islands.c b/delta-islands.c\nnew file mode 100644\nindex 0000000000..645fe966c5\n--- /dev/null\n+++ b/delta-islands.c\n@@ -0,0 +1,490 @@\n+#include \"builtin.h\"\n+#include \"cache.h\"\n+#include \"attr.h\"\n+#include \"object.h\"\n+#include \"blob.h\"\n+#include \"commit.h\"\n+#include \"tag.h\"\n+#include \"tree.h\"\n+#include \"delta.h\"\n+#include \"pack.h\"\n+#include \"tree-walk.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"list-objects.h\"\n+#include \"progress.h\"\n+#include \"refs.h\"\n+#include \"khash.h\"\n+#include \"pack-bitmap.h\"\n+#include \"pack-objects.h\"\n+#include \"delta-islands.h\"\n+#include \"sha1-array.h\"\n+#include \"config.h\"\n+\n+KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)\n+\n+static khash_sha1 *island_marks;\n+static unsigned island_counter;\n+static unsigned island_counter_core;\n+\n+static kh_str_t *remote_islands;\n+\n+struct remote_island {\n+\tuint64_t hash;\n+\tstruct oid_array oids;\n+};\n+\n+struct island_bitmap {\n+\tuint32_t refcount;\n+\tuint32_t bits[];\n+};\n+\n+static uint32_t island_bitmap_size;\n+\n+/*\n+ * Allocate a new bitmap; if \"old\" is not NULL, the new bitmap will be a copy\n+ * of \"old\". Otherwise, the new bitmap is empty.\n+ */\n+static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old)\n+{\n+\tsize_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4);\n+\tstruct island_bitmap *b = xcalloc(1, size);\n+\n+\tif (old)\n+\t\tmemcpy(b, old, size);\n+\n+\tb->refcount = 1;\n+\treturn b;\n+}\n+\n+static void island_bitmap_or(struct island_bitmap *a, const struct island_bitmap *b)\n+{\n+\tuint32_t i;\n+\n+\tfor (i = 0; i < island_bitmap_size; ++i)\n+\t\ta->bits[i] |= b->bits[i];\n+}\n+\n+static int island_bitmap_is_subset(struct island_bitmap *self,\n+\t\tstruct island_bitmap *super)\n+{\n+\tuint32_t i;\n+\n+\tif (self == super)\n+\t\treturn 1;\n+\n+\tfor (i = 0; i < island_bitmap_size; ++i) {\n+\t\tif ((self->bits[i] & super->bits[i]) != self->bits[i])\n+\t\t\treturn 0;\n+\t}\n+\n+\treturn 1;\n+}\n+\n+#define ISLAND_BITMAP_BLOCK(x) (x / 32)\n+#define ISLAND_BITMAP_MASK(x) (1 << (x % 32))\n+\n+static void island_bitmap_set(struct island_bitmap *self, uint32_t i)\n+{\n+\tself->bits[ISLAND_BITMAP_BLOCK(i)] |= ISLAND_BITMAP_MASK(i);\n+}\n+\n+static int island_bitmap_get(struct island_bitmap *self, uint32_t i)\n+{\n+\treturn (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0;\n+}\n+\n+int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)\n+{\n+\tkhiter_t trg_pos, src_pos;\n+\n+\t/* If we aren't using islands, assume everything goes together. */\n+\tif (!island_marks)\n+\t\treturn 1;\n+\n+\t/*\n+\t * If we don't have a bitmap for the target, we can delta it\n+\t * against anything -- it's not an important object\n+\t */\n+\ttrg_pos = kh_get_sha1(island_marks, trg_oid->hash);\n+\tif (trg_pos >= kh_end(island_marks))\n+\t\treturn 1;\n+\n+\t/*\n+\t * if the source (our delta base) doesn't have a bitmap,\n+\t * we don't want to base any deltas on it!\n+\t */\n+\tsrc_pos = kh_get_sha1(island_marks, src_oid->hash);\n+\tif (src_pos >= kh_end(island_marks))\n+\t\treturn 0;\n+\n+\treturn island_bitmap_is_subset(kh_value(island_marks, trg_pos),\n+\t\t\t\tkh_value(island_marks, src_pos));\n+}\n+\n+int island_delta_cmp(const struct object_id *a, const struct object_id *b)\n+{\n+\tkhiter_t a_pos, b_pos;\n+\tstruct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL;\n+\n+\tif (!island_marks)\n+\t\treturn 0;\n+\n+\ta_pos = kh_get_sha1(island_marks, a->hash);\n+\tif (a_pos < kh_end(island_marks))\n+\t\ta_bitmap = kh_value(island_marks, a_pos);\n+\n+\tb_pos = kh_get_sha1(island_marks, b->hash);\n+\tif (b_pos < kh_end(island_marks))\n+\t\tb_bitmap = kh_value(island_marks, b_pos);\n+\n+\tif (a_bitmap) {\n+\t\tif (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap))\n+\t\t\treturn -1;\n+\t}\n+\tif (b_bitmap) {\n+\t\tif (!a_bitmap || !island_bitmap_is_subset(b_bitmap, a_bitmap))\n+\t\t\treturn 1;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static struct island_bitmap *create_or_get_island_marks(struct object *obj)\n+{\n+\tkhiter_t pos;\n+\tint hash_ret;\n+\n+\tpos = kh_put_sha1(island_marks, obj->oid.hash, &hash_ret);\n+\tif (hash_ret)\n+\t\tkh_value(island_marks, pos) = island_bitmap_new(NULL);\n+\n+\treturn kh_value(island_marks, pos);\n+}\n+\n+static void set_island_marks(struct object *obj, struct island_bitmap *marks)\n+{\n+\tstruct island_bitmap *b;\n+\tkhiter_t pos;\n+\tint hash_ret;\n+\n+\tpos = kh_put_sha1(island_marks, obj->oid.hash, &hash_ret);\n+\tif (hash_ret) {\n+\t\t/*\n+\t\t * We don't have one yet; make a copy-on-write of the\n+\t\t * parent.\n+\t\t */\n+\t\tmarks->refcount++;\n+\t\tkh_value(island_marks, pos) = marks;\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * We do have it. Make sure we split any copy-on-write before\n+\t * updating.\n+\t */\n+\tb = kh_value(island_marks, pos);\n+\tif (b->refcount > 1) {\n+\t\tb->refcount--;\n+\t\tb = kh_value(island_marks, pos) = island_bitmap_new(b);\n+\t}\n+\tisland_bitmap_or(b, marks);\n+}\n+\n+static void mark_remote_island_1(struct remote_island *rl, int is_core_island)\n+{\n+\tuint32_t i;\n+\n+\tfor (i = 0; i < rl->oids.nr; ++i) {\n+\t\tstruct island_bitmap *marks;\n+\t\tstruct object *obj = parse_object(&rl->oids.oid[i]);\n+\n+\t\tif (!obj)\n+\t\t\tcontinue;\n+\n+\t\tmarks = create_or_get_island_marks(obj);\n+\t\tisland_bitmap_set(marks, island_counter);\n+\n+\t\tif (is_core_island && obj->type == OBJ_COMMIT)\n+\t\t\tobj->flags |= NEEDS_BITMAP;\n+\n+\t\t/* If it was a tag, also make sure we hit the underlying object. */\n+\t\twhile (obj && obj->type == OBJ_TAG) {\n+\t\t\tobj = ((struct tag *)obj)->tagged;\n+\t\t\tif (obj) {\n+\t\t\t\tparse_object(&obj->oid);\n+\t\t\t\tmarks = create_or_get_island_marks(obj);\n+\t\t\t\tisland_bitmap_set(marks, island_counter);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tif (is_core_island)\n+\t\tisland_counter_core = island_counter;\n+\n+\tisland_counter++;\n+}\n+\n+static int cmp_tree_depth(const void *va, const void *vb)\n+{\n+\tstruct object_entry *a = *(struct object_entry **)va;\n+\tstruct object_entry *b = *(struct object_entry **)vb;\n+\treturn a->tree_depth - b->tree_depth;\n+}\n+\n+void resolve_tree_islands(int progress, struct packing_data *to_pack)\n+{\n+\tstruct progress *progress_state = NULL;\n+\tstruct object_entry **todo;\n+\tint nr = 0;\n+\tint i;\n+\n+\tif (!island_marks)\n+\t\treturn;\n+\n+\t/*\n+\t * We process only trees, as commits and tags have already been handled\n+\t * (and passed their marks on to root trees, as well. We must make sure\n+\t * to process them in descending tree-depth order so that marks\n+\t * propagate down the tree properly, even if a sub-tree is found in\n+\t * multiple parent trees.\n+\t */\n+\ttodo = xmalloc(to_pack->nr_objects * sizeof(*todo));\n+\tfor (i = 0; i < to_pack->nr_objects; i++) {\n+\t\tif (oe_type(&to_pack->objects[i]) == OBJ_TREE)\n+\t\t\ttodo[nr++] = &to_pack->objects[i];\n+\t}\n+\tqsort(todo, nr, sizeof(*todo), cmp_tree_depth);\n+\n+\tif (progress)\n+\t\tprogress_state = start_progress(\"Propagating island marks\", nr);\n+\n+\tfor (i = 0; i < nr; i++) {\n+\t\tstruct object_entry *ent = todo[i];\n+\t\tstruct island_bitmap *root_marks;\n+\t\tstruct tree *tree;\n+\t\tstruct tree_desc desc;\n+\t\tstruct name_entry entry;\n+\t\tkhiter_t pos;\n+\n+\t\tpos = kh_get_sha1(island_marks, ent->idx.oid.hash);\n+\t\tif (pos >= kh_end(island_marks))\n+\t\t\tcontinue;\n+\n+\t\troot_marks = kh_value(island_marks, pos);\n+\n+\t\ttree = lookup_tree(&ent->idx.oid);\n+\t\tif (!tree || parse_tree(tree) < 0)\n+\t\t\tdie(\"bad tree object %s\", oid_to_hex(&ent->idx.oid));\n+\n+\t\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\t\twhile (tree_entry(&desc, &entry)) {\n+\t\t\tstruct object *obj;\n+\n+\t\t\tif (S_ISGITLINK(entry.mode))\n+\t\t\t\tcontinue;\n+\n+\t\t\tobj = lookup_object(entry.oid->hash);\n+\t\t\tif (!obj)\n+\t\t\t\tcontinue;\n+\n+\t\t\tset_island_marks(obj, root_marks);\n+\t\t}\n+\n+\t\tfree(tree->buffer);\n+\t\ttree->buffer = NULL;\n+\t\ttree->object.parsed = 0;\n+\n+\t\tdisplay_progress(progress_state, i+1);\n+\t}\n+\n+\tstop_progress(&progress_state);\n+\tfree(todo);\n+}\n+\n+static regex_t *island_regexes;\n+static unsigned int island_regexes_alloc, island_regexes_nr;\n+static const char *core_island_name;\n+\n+static int island_config_callback(const char *k, const char *v, void *cb)\n+{\n+\tif (!strcmp(k, \"pack.island\")) {\n+\t\tstruct strbuf re = STRBUF_INIT;\n+\n+\t\tif (!v)\n+\t\t\treturn config_error_nonbool(k);\n+\n+\t\tif (island_regexes_nr >= island_regexes_alloc) {\n+\t\t\tisland_regexes_alloc = (island_regexes_alloc + 8) * 2;\n+\t\t\tisland_regexes = xrealloc(island_regexes,\n+\t\t\t\t\tisland_regexes_alloc * sizeof(regex_t));\n+\t\t}\n+\n+\t\tif (*v != '^')\n+\t\t\tstrbuf_addch(&re, '^');\n+\t\tstrbuf_addstr(&re, v);\n+\n+\t\tif (regcomp(&island_regexes[island_regexes_nr], re.buf, REG_EXTENDED))\n+\t\t\tdie(\"failed to load island regex for '%s': %s\", k, re.buf);\n+\n+\t\tstrbuf_release(&re);\n+\t\tisland_regexes_nr++;\n+\t\treturn 0;\n+\t}\n+\n+\tif (!strcmp(k, \"pack.islandcore\"))\n+\t\treturn git_config_string(&core_island_name, k, v);\n+\n+\treturn 0;\n+}\n+\n+static void add_ref_to_island(const char *island_name, const struct object_id *oid)\n+{\n+\tuint64_t sha_core;\n+\tstruct remote_island *rl = NULL;\n+\n+\tint hash_ret;\n+\tkhiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret);\n+\n+\tif (hash_ret) {\n+\t\tkh_key(remote_islands, pos) = xstrdup(island_name);\n+\t\tkh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island));\n+\t}\n+\n+\trl = kh_value(remote_islands, pos);\n+\toid_array_append(&rl->oids, oid);\n+\n+\tmemcpy(&sha_core, oid->hash, sizeof(uint64_t));\n+\trl->hash += sha_core;\n+}\n+\n+static int find_island_for_ref(const char *refname, const struct object_id *oid,\n+\t\t\t int flags, void *data)\n+{\n+\tint i, m;\n+\tregmatch_t matches[8];\n+\tstruct strbuf island_name = STRBUF_INIT;\n+\n+\t/* walk backwards to get last-one-wins ordering */\n+\tfor (i = island_regexes_nr - 1; i >= 0; i--) {\n+\t\tif (!regexec(&island_regexes[i], refname,\n+\t\t\t ARRAY_SIZE(matches), matches, 0))\n+\t\t\tbreak;\n+\t}\n+\n+\tif (i < 0)\n+\t\treturn 0;\n+\n+\tfor (m = 1; m < ARRAY_SIZE(matches); m++) {\n+\t\tregmatch_t *match = &matches[m];\n+\n+\t\tif (match->rm_so == -1)\n+\t\t\tcontinue;\n+\n+\t\tif (island_name.len)\n+\t\t\tstrbuf_addch(&island_name, '-');\n+\n+\t\tstrbuf_add(&island_name, refname + match->rm_so, match->rm_eo - match->rm_so);\n+\t}\n+\n+\tadd_ref_to_island(island_name.buf, oid);\n+\tstrbuf_release(&island_name);\n+\treturn 0;\n+}\n+\n+static struct remote_island *get_core_island(void)\n+{\n+\tif (core_island_name) {\n+\t\tkhiter_t pos = kh_get_str(remote_islands, core_island_name);\n+\t\tif (pos < kh_end(remote_islands))\n+\t\t\treturn kh_value(remote_islands, pos);\n+\t}\n+\n+\treturn NULL;\n+}\n+\n+static void deduplicate_islands(void)\n+{\n+\tstruct remote_island *island, *core = NULL, **list;\n+\tunsigned int island_count, dst, src, ref, i = 0;\n+\n+\tisland_count = kh_size(remote_islands);\n+\tlist = xmalloc(island_count * sizeof(struct remote_island *));\n+\n+\tkh_foreach_value(remote_islands, island, {\n+\t\tlist[i++] = island;\n+\t});\n+\n+\tfor (ref = 0; ref + 1 < island_count; ref++) {\n+\t\tfor (src = ref + 1, dst = src; src < island_count; src++) {\n+\t\t\tif (list[ref]->hash == list[src]->hash)\n+\t\t\t\tcontinue;\n+\n+\t\t\tif (src != dst)\n+\t\t\t\tlist[dst] = list[src];\n+\n+\t\t\tdst++;\n+\t\t}\n+\t\tisland_count = dst;\n+\t}\n+\n+\tisland_bitmap_size = (island_count / 32) + 1;\n+\tcore = get_core_island();\n+\n+\tfor (i = 0; i < island_count; ++i) {\n+\t\tmark_remote_island_1(list[i], core && list[i]->hash == core->hash);\n+\t}\n+\n+\tfree(list);\n+}\n+\n+void load_delta_islands(void)\n+{\n+\tisland_marks = kh_init_sha1();\n+\tremote_islands = kh_init_str();\n+\n+\tgit_config(island_config_callback, NULL);\n+\tfor_each_ref(find_island_for_ref, NULL);\n+\tdeduplicate_islands();\n+\n+\tfprintf(stderr, \"Marked %d islands, done.\\n\", island_counter);\n+}\n+\n+void propagate_island_marks(struct commit *commit)\n+{\n+\tkhiter_t pos = kh_get_sha1(island_marks, commit->object.oid.hash);\n+\n+\tif (pos < kh_end(island_marks)) {\n+\t\tstruct commit_list *p;\n+\t\tstruct island_bitmap *root_marks = kh_value(island_marks, pos);\n+\n+\t\tparse_commit(commit);\n+\t\tset_island_marks(&get_commit_tree(commit)->object, root_marks);\n+\t\tfor (p = commit->parents; p; p = p->next)\n+\t\t\tset_island_marks(&p->item->object, root_marks);\n+\t}\n+}\n+\n+int compute_pack_layers(struct packing_data *to_pack)\n+{\n+\tuint32_t i;\n+\n+\tif (!core_island_name || !island_marks)\n+\t\treturn 1;\n+\n+\tfor (i = 0; i < to_pack->nr_objects; ++i) {\n+\t\tstruct object_entry *entry = &to_pack->objects[i];\n+\t\tkhiter_t pos = kh_get_sha1(island_marks, entry->idx.oid.hash);\n+\n+\t\tentry->layer = 1;\n+\n+\t\tif (pos < kh_end(island_marks)) {\n+\t\t\tstruct island_bitmap *bitmap = kh_value(island_marks, pos);\n+\n+\t\t\tif (island_bitmap_get(bitmap, island_counter_core))\n+\t\t\t\tentry->layer = 0;\n+\t\t}\n+\t}\n+\n+\treturn 2;\n+}\ndiff --git a/delta-islands.h b/delta-islands.h\nnew file mode 100644\nindex 0000000000..f9725730f4\n--- /dev/null\n+++ b/delta-islands.h\n@@ -0,0 +1,11 @@\n+#ifndef DELTA_ISLANDS_H\n+#define DELTA_ISLANDS_H\n+\n+int island_delta_cmp(const struct object_id *a, const struct object_id *b);\n+int in_same_island(const struct object_id *, const struct object_id *);\n+void resolve_tree_islands(int progress, struct packing_data *to_pack);\n+void load_delta_islands(void);\n+void propagate_island_marks(struct commit *commit);\n+int compute_pack_layers(struct packing_data *to_pack);\n+\n+#endif /* DELTA_ISLANDS_H */\ndiff --git a/pack-objects.h b/pack-objects.h\nindex edf74dabdd..8eecd67991 100644\n--- a/pack-objects.h\n+++ b/pack-objects.h\n@@ -100,6 +100,10 @@ struct object_entry {\n \tunsigned type_:TYPE_BITS;\n \tunsigned no_try_delta:1;\n \tunsigned in_pack_type:TYPE_BITS; /* could be delta */\n+\n+\tunsigned int tree_depth; /* should be repositioned for packing? */\n+\tunsigned char layer;\n+\n \tunsigned preferred_base:1; /*\n \t\t\t\t * we do not pack this, but is available\n \t\t\t\t * to be used as the base object to delta\n-- \n2.18.0.237.gffdb1dbdaa\n\n"},{"id":"353291","messageId":"20180722054836.28935-5-chriscool@tuxfamily.org","threadId":"48935","inReplyTo":"20180722054836.28935-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 4/5] repack: add delta-islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-07-22T05:48:35Z","receivedAt":"2018-07-22T05:49:06Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nImplement simple support for --delta-islands option and\nrepack.useDeltaIslands config variable in git repack.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Documentation/config.txt | 4 ++++\n Documentation/git-repack.txt | 5 +++++\n builtin/repack.c | 9 +++++++++\n 3 files changed, 18 insertions(+)\n\ndiff --git a/Documentation/config.txt b/Documentation/config.txt\nindex f682e92a1a..1da39da2a6 100644\n--- a/Documentation/config.txt\n+++ b/Documentation/config.txt\n@@ -3091,6 +3091,10 @@ repack.packKeptObjects::\n \tindex is being written (either via `--write-bitmap-index` or\n \t`repack.writeBitmaps`).\n \n+repack.useDeltaIslands::\n+\tIf set to true, makes `git repack` act as if `--delta-islands`\n+\twas passed. Defaults to `false`.\n+\n repack.writeBitmaps::\n \tWhen true, git will write a bitmap index when packing all\n \tobjects to disk (e.g., when `git repack -a` is run). This\ndiff --git a/Documentation/git-repack.txt b/Documentation/git-repack.txt\nindex d90e7907f4..a8b2d4722f 100644\n--- a/Documentation/git-repack.txt\n+++ b/Documentation/git-repack.txt\n@@ -155,6 +155,11 @@ depth is 4095.\n \tbeing removed. In addition, any unreachable loose objects will\n \tbe packed (and their loose counterparts removed).\n \n+-i::\n+--delta-islands::\n+\tPass the `--delta-islands` option to `git-pack-objects`, see\n+\tlinkgit:git-pack-objects[1].\n+\n Configuration\n -------------\n \ndiff --git a/builtin/repack.c b/builtin/repack.c\nindex 6c636e159e..5ab9ee69e4 100644\n--- a/builtin/repack.c\n+++ b/builtin/repack.c\n@@ -12,6 +12,7 @@\n static int delta_base_offset = 1;\n static int pack_kept_objects = -1;\n static int write_bitmaps;\n+static int use_delta_islands;\n static char *packdir, *packtmp;\n \n static const char *const git_repack_usage[] = {\n@@ -40,6 +41,10 @@ static int repack_config(const char *var, const char *value, void *cb)\n \t\twrite_bitmaps = git_config_bool(var, value);\n \t\treturn 0;\n \t}\n+\tif (!strcmp(var, \"repack.usedeltaislands\")) {\n+\t\tuse_delta_islands = git_config_bool(var, value);\n+\t\treturn 0;\n+\t}\n \treturn git_default_config(var, value, cb);\n }\n \n@@ -194,6 +199,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\t\t\tN_(\"pass --local to git-pack-objects\")),\n \t\tOPT_BOOL('b', \"write-bitmap-index\", &write_bitmaps,\n \t\t\t\tN_(\"write bitmap index\")),\n+\t\tOPT_BOOL('i', \"delta-islands\", &use_delta_islands,\n+\t\t\t\tN_(\"pass --delta-islands to git-pack-objects\")),\n \t\tOPT_STRING(0, \"unpack-unreachable\", &unpack_unreachable, N_(\"approxidate\"),\n \t\t\t\tN_(\"with -A, do not loosen objects older than this\")),\n \t\tOPT_BOOL('k', \"keep-unreachable\", &keep_unreachable,\n@@ -267,6 +274,8 @@ int cmd_repack(int argc, const char **argv, const char *prefix)\n \t\targv_array_pushf(&cmd.args, \"--no-reuse-object\");\n \tif (write_bitmaps)\n \t\targv_array_push(&cmd.args, \"--write-bitmap-index\");\n+\tif (use_delta_islands)\n+\t\targv_array_push(&cmd.args, \"--delta-islands\");\n \n \tif (pack_everything & ALL_INTO_ONE) {\n \t\tget_non_kept_pack_filenames(&existing_packs, &keep_pack_list);\n-- \n2.18.0.237.gffdb1dbdaa\n\n"},{"id":"353292","messageId":"20180722054836.28935-6-chriscool@tuxfamily.org","threadId":"48935","inReplyTo":"20180722054836.28935-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 5/5] t: add t9930-delta-islands.sh","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-07-22T05:48:36Z","receivedAt":"2018-07-22T05:49:07Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n t/t9930-delta-islands.sh | 143 +++++++++++++++++++++++++++++++++++++++\n 1 file changed, 143 insertions(+)\n create mode 100755 t/t9930-delta-islands.sh\n\ndiff --git a/t/t9930-delta-islands.sh b/t/t9930-delta-islands.sh\nnew file mode 100755\nindex 0000000000..fea92a5777\n--- /dev/null\n+++ b/t/t9930-delta-islands.sh\n@@ -0,0 +1,143 @@\n+#!/bin/sh\n+\n+test_description='exercise delta islands'\n+. ./test-lib.sh\n+\n+# returns true iff $1 is a delta based on $2\n+is_delta_base () {\n+\tdelta_base=$(echo \"$1\" | git cat-file --batch-check='%(deltabase)') &&\n+\techo >&2 \"$1 has base $delta_base\" &&\n+\ttest \"$delta_base\" = \"$2\"\n+}\n+\n+# generate a commit on branch $1 with a single file, \"file\", whose\n+# content is mostly based on the seed $2, but with a unique bit\n+# of content $3 appended. This should allow us to see whether\n+# blobs of different refs delta against each other.\n+commit() {\n+\tblob=$({ test-tool genrandom \"$2\" 10240 && echo \"$3\"; } |\n+\t git hash-object -w --stdin) &&\n+\ttree=$(printf '100644 blob %s\\tfile\\n' \"$blob\" | git mktree) &&\n+\tcommit=$(echo \"$2-$3\" | git commit-tree \"$tree\" ${4:+-p \"$4\"}) &&\n+\tgit update-ref \"refs/heads/$1\" \"$commit\" &&\n+\teval \"$1\"'=$(git rev-parse $1:file)' &&\n+\teval \"echo >&2 $1=\\$$1\"\n+}\n+\n+test_expect_success 'setup commits' '\n+\tcommit one seed 1 &&\n+\tcommit two seed 12\n+'\n+\n+# Note: This is heavily dependent on the \"prefer larger objects as base\"\n+# heuristic.\n+test_expect_success 'vanilla repack deltas one against two' '\n+\tgit repack -adf &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'island repack with no island definition is vanilla' '\n+\tgit repack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'island repack with no matches is vanilla' '\n+\tgit -c \"pack.island=refs/foo\" repack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'separate islands disallows delta' '\n+\tgit -c \"pack.island=refs/heads/(.*)\" repack -adfi &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'same island allows delta' '\n+\tgit -c \"pack.island=refs/heads\" repack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'coalesce same-named islands' '\n+\tgit \\\n+\t\t-c \"pack.island=refs/(.*)/one\" \\\n+\t\t-c \"pack.island=refs/(.*)/two\" \\\n+\t\trepack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'island restrictions drop reused deltas' '\n+\tgit repack -adfi &&\n+\tis_delta_base $one $two &&\n+\tgit -c \"pack.island=refs/heads/(.*)\" repack -adi &&\n+\t! is_delta_base $one $two &&\n+\t! is_delta_base $two $one\n+'\n+\n+test_expect_success 'island regexes are left-anchored' '\n+\tgit -c \"pack.island=heads/(.*)\" repack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'island regexes follow last-one-wins scheme' '\n+\tgit \\\n+\t\t-c \"pack.island=refs/heads/(.*)\" \\\n+\t\t-c \"pack.island=refs/heads/\" \\\n+\t\trepack -adfi &&\n+\tis_delta_base $one $two\n+'\n+\n+test_expect_success 'setup shared history' '\n+\tcommit root shared root &&\n+\tcommit one shared 1 root &&\n+\tcommit two shared 12-long root\n+'\n+\n+# We know that $two will be preferred as a base from $one,\n+# because we can transform it with a pure deletion.\n+#\n+# We also expect $root as a delta against $two by the \"longest is base\" rule.\n+test_expect_success 'vanilla delta goes between branches' '\n+\tgit repack -adf &&\n+\tis_delta_base $one $two &&\n+\tis_delta_base $root $two\n+'\n+\n+# Here we should allow $one to base itself on $root; even though\n+# they are in different islands, the objects in $root are in a superset\n+# of islands compared to those in $one.\n+#\n+# Similarly, $two can delta against $root by our rules. And unlike $one,\n+# in which we are just allowing it, the island rules actually put $root\n+# as a possible base for $two, which it would not otherwise be (due to the size\n+# sorting).\n+test_expect_success 'deltas allowed against superset islands' '\n+\tgit -c \"pack.island=refs/heads/(.*)\" repack -adfi &&\n+\tis_delta_base $one $root &&\n+\tis_delta_base $two $root\n+'\n+\n+# We are going to test the packfile order here, so we again have to make some\n+# assumptions. We assume that \"$root\", as part of our core \"one\", must come\n+# before \"$two\". This should be guaranteed by the island code. However, for\n+# this test to fail without islands, we are also assuming that it would not\n+# otherwise do so. This is true by the current write order, which will put\n+# commits (and their contents) before their parents.\n+test_expect_success 'island core places core objects first' '\n+\tcat >expect <<-EOF &&\n+\t$root\n+\t$two\n+\tEOF\n+\tgit -c \"pack.island=refs/heads/(.*)\" \\\n+\t -c \"pack.islandcore=one\" \\\n+\t repack -adfi &&\n+\tgit verify-pack -v .git/objects/pack/*.pack |\n+\tcut -d\" \" -f1 |\n+\tegrep \"$root|$two\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'unmatched island core is not fatal' '\n+\tgit -c \"pack.islandcore=one\" repack -adfi\n+'\n+\n+test_done\n-- \n2.18.0.237.gffdb1dbdaa\n\n"},{"id":"353293","messageId":"20180722054836.28935-4-chriscool@tuxfamily.org","threadId":"48935","inReplyTo":"20180722054836.28935-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-07-22T05:48:34Z","receivedAt":"2018-07-22T05:49:08Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nImplement support for delta islands in git pack-objects\nand document how delta islands work in\n\"Documentation/git-pack-objects.txt\".\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Documentation/git-pack-objects.txt | 88 +++++++++++++++++++\n builtin/pack-objects.c | 130 ++++++++++++++++++++---------\n 2 files changed, 177 insertions(+), 41 deletions(-)\n\ndiff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt\nindex d95b472d16..7b7a36056f 100644\n--- a/Documentation/git-pack-objects.txt\n+++ b/Documentation/git-pack-objects.txt\n@@ -289,6 +289,94 @@ Unexpected missing object will raise an error.\n --unpack-unreachable::\n \tKeep unreachable objects in loose form. This implies `--revs`.\n \n+--delta-islands::\n+\tRestrict delta matches based on \"islands\". See DELTA ISLANDS\n+\tbelow.\n+\n+\n+DELTA ISLANDS\n+-------------\n+\n+When possible, `pack-objects` tries to reuse existing on-disk deltas to\n+avoid having to search for new ones on the fly. This is an important\n+optimization for serving fetches, because it means the server can avoid\n+inflating most objects at all and just send the bytes directly from\n+disk. This optimization can't work when an object is stored as a delta\n+against a base which the receiver does not have (and which we are not\n+already sending). In that case the server \"breaks\" the delta and has to\n+find a new one, which has a high CPU cost. Therefore it's important for\n+performance that the set of objects in on-disk delta relationships match\n+what a client would fetch.\n+\n+In a normal repository, this tends to work automatically. The objects\n+are mostly reachable from the branches and tags, and that's what clients\n+fetch. Any deltas we find on the server are likely to be between objects\n+the client has or will have.\n+\n+But in some repository setups, you may have several related but separate\n+groups of ref tips, with clients tending to fetch those groups\n+independently. For example, imagine that you are hosting several \"forks\"\n+of a repository in a single shared object store, and letting clients\n+view them as separate repositories through `GIT_NAMESPACE` or separate\n+repos using the alternates mechanism. A naive repack may find that the\n+optimal delta for an object is against a base that is only found in\n+another fork. But when a client fetches, they will not have the base\n+object, and we'll have to find a new delta on the fly.\n+\n+A similar situation may exist if you have many refs outside of\n+`refs/heads/` and `refs/tags/` that point to related objects (e.g.,\n+`refs/pull` or `refs/changes` used by some hosting providers). By\n+default, clients fetch only heads and tags, and deltas against objects\n+found only in those other groups cannot be sent as-is.\n+\n+Delta islands solve this problem by allowing you to group your refs into\n+distinct \"islands\". Pack-objects computes which objects are reachable\n+from which islands, and refuses to make a delta from an object `A`\n+against a base which is not present in all of `A`'s islands. This\n+results in slightly larger packs (because we miss some delta\n+opportunities), but guarantees that a fetch of one island will not have\n+to recompute deltas on the fly due to crossing island boundaries.\n+\n+Islands are configured via the `pack.island` option, which can be\n+specified multiple times. Each value is a left-anchored regular\n+expressions matching refnames. For example:\n+\n+-------------------------------------------\n+[pack]\n+island = refs/heads/\n+island = refs/tags/\n+-------------------------------------------\n+\n+puts heads and tags into an island (whose name is the empty string; see\n+below for more on naming). Any refs which do not match those regular\n+expressions (e.g., `refs/pull/123`) is not in any island. Any object\n+which is reachable only from `refs/pull/` (but not heads or tags) is\n+therefore not a candidate to be used as a base for `refs/heads/`.\n+\n+Refs are grouped into islands based on their \"names\", and two regexes\n+that produce the same name are considered to be in the same island. The\n+names are computed from the regexes by concatenating any capture groups\n+from the regex (and if there are none, then the name is the empty\n+string, as in the above example). This allows you to create arbitrary\n+numbers of islands. For example, imagine you store the refs for each\n+fork in `refs/virtual/ID`, where `ID` is a numeric identifier. You might\n+then configure:\n+\n+-------------------------------------------\n+[pack]\n+island = refs/virtual/([0-9]+)/heads/\n+island = refs/virtual/([0-9]+)/tags/\n+island = refs/virtual/([0-9]+)/(pull)/\n+-------------------------------------------\n+\n+That puts the heads and tags for each fork in their own island (named\n+\"1234\" or similar), and the pull refs for each go into their own\n+\"1234-pull\".\n+\n+Note that we pick a single island for each regex to go into, using \"last\n+one wins\" ordering (which allows repo-specific config to take precedence\n+over user-wide config, and so forth).\n+\n SEE ALSO\n --------\n linkgit:git-rev-list[1]\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex ebc8cefb53..3bd41d8b05 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -24,6 +24,7 @@\n #include \"streaming.h\"\n #include \"thread-utils.h\"\n #include \"pack-bitmap.h\"\n+#include \"delta-islands.h\"\n #include \"reachable.h\"\n #include \"sha1-array.h\"\n #include \"argv-array.h\"\n@@ -59,6 +60,7 @@ static struct packing_data to_pack;\n \n static struct pack_idx_entry **written_list;\n static uint32_t nr_result, nr_written, nr_seen;\n+static uint32_t write_layer;\n \n static int non_empty;\n static int reuse_delta = 1, reuse_object = 1;\n@@ -93,6 +95,8 @@ static uint16_t write_bitmap_options;\n \n static int exclude_promisor_objects;\n \n+static int use_delta_islands;\n+\n static unsigned long delta_cache_size = 0;\n static unsigned long max_delta_cache_size = DEFAULT_DELTA_CACHE_SIZE;\n static unsigned long cache_max_small_delta_size = 1000;\n@@ -607,7 +611,7 @@ static inline void add_to_write_order(struct object_entry **wo,\n \t\t\t unsigned int *endp,\n \t\t\t struct object_entry *e)\n {\n-\tif (e->filled)\n+\tif (e->filled || e->layer != write_layer)\n \t\treturn;\n \two[(*endp)++] = e;\n \te->filled = 1;\n@@ -669,6 +673,7 @@ static void add_family_to_write_order(struct object_entry **wo,\n \n static struct object_entry **compute_write_order(void)\n {\n+\tuint32_t max_layers = 1;\n \tunsigned int i, wo_end, last_untagged;\n \n \tstruct object_entry **wo;\n@@ -700,51 +705,58 @@ static struct object_entry **compute_write_order(void)\n \t */\n \tfor_each_tag_ref(mark_tagged, NULL);\n \n-\t/*\n-\t * Give the objects in the original recency order until\n-\t * we see a tagged tip.\n-\t */\n+\tif (use_delta_islands)\n+\t\tmax_layers = compute_pack_layers(&to_pack);\n+\n \tALLOC_ARRAY(wo, to_pack.nr_objects);\n-\tfor (i = wo_end = 0; i < to_pack.nr_objects; i++) {\n-\t\tif (objects[i].tagged)\n-\t\t\tbreak;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n-\t}\n-\tlast_untagged = i;\n+\two_end = 0;\n \n-\t/*\n-\t * Then fill all the tagged tips.\n-\t */\n-\tfor (; i < to_pack.nr_objects; i++) {\n-\t\tif (objects[i].tagged)\n+\tfor (; write_layer < max_layers; ++write_layer) {\n+\t\t/*\n+\t\t * Give the objects in the original recency order until\n+\t\t * we see a tagged tip.\n+\t\t */\n+\t\tfor (i = 0; i < to_pack.nr_objects; i++) {\n+\t\t\tif (objects[i].tagged)\n+\t\t\t\tbreak;\n \t\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n-\t}\n+\t\t}\n+\t\tlast_untagged = i;\n \n-\t/*\n-\t * And then all remaining commits and tags.\n-\t */\n-\tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n-\t\tif (oe_type(&objects[i]) != OBJ_COMMIT &&\n-\t\t oe_type(&objects[i]) != OBJ_TAG)\n-\t\t\tcontinue;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n-\t}\n+\t\t/*\n+\t\t * Then fill all the tagged tips.\n+\t\t */\n+\t\tfor (; i < to_pack.nr_objects; i++) {\n+\t\t\tif (objects[i].tagged)\n+\t\t\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\t}\n \n-\t/*\n-\t * And then all the trees.\n-\t */\n-\tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n-\t\tif (oe_type(&objects[i]) != OBJ_TREE)\n-\t\t\tcontinue;\n-\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n-\t}\n+\t\t/*\n+\t\t * And then all remaining commits and tags.\n+\t\t */\n+\t\tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n+\t\t\tif (oe_type(&objects[i]) != OBJ_COMMIT &&\n+\t\t\t oe_type(&objects[i]) != OBJ_TAG)\n+\t\t\t\tcontinue;\n+\t\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\t}\n \n-\t/*\n-\t * Finally all the rest in really tight order\n-\t */\n-\tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n-\t\tif (!objects[i].filled)\n-\t\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n+\t\t/*\n+\t\t * And then all the trees.\n+\t\t */\n+\t\tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n+\t\t\tif (oe_type(&objects[i]) != OBJ_TREE)\n+\t\t\t\tcontinue;\n+\t\t\tadd_to_write_order(wo, &wo_end, &objects[i]);\n+\t\t}\n+\n+\t\t/*\n+\t\t * Finally all the rest in really tight order\n+\t\t */\n+\t\tfor (i = last_untagged; i < to_pack.nr_objects; i++) {\n+\t\t\tif (!objects[i].filled && objects[i].layer == write_layer)\n+\t\t\t\tadd_family_to_write_order(wo, &wo_end, &objects[i]);\n+\t\t}\n \t}\n \n \tif (wo_end != to_pack.nr_objects)\n@@ -1504,7 +1516,8 @@ static void check_object(struct object_entry *entry)\n \t\t\tbreak;\n \t\t}\n \n-\t\tif (base_ref && (base_entry = packlist_find(&to_pack, base_ref, NULL))) {\n+\t\tif (base_ref && (base_entry = packlist_find(&to_pack, base_ref, NULL)) &&\n+\t\t in_same_island(&entry->idx.oid, &base_entry->idx.oid)) {\n \t\t\t/*\n \t\t\t * If base_ref was set above that means we wish to\n \t\t\t * reuse delta data, and we even found that base\n@@ -1820,6 +1833,11 @@ static int type_size_sort(const void *_a, const void *_b)\n \t\treturn -1;\n \tif (a->preferred_base < b->preferred_base)\n \t\treturn 1;\n+\tif (use_delta_islands) {\n+\t\tint island_cmp = island_delta_cmp(&a->idx.oid, &b->idx.oid);\n+\t\tif (island_cmp)\n+\t\t\treturn island_cmp;\n+\t}\n \tif (a_size > b_size)\n \t\treturn -1;\n \tif (a_size < b_size)\n@@ -1968,6 +1986,9 @@ static int try_delta(struct unpacked *trg, struct unpacked *src,\n \tif (trg_size < src_size / 32)\n \t\treturn 0;\n \n+\tif (!in_same_island(&trg->entry->idx.oid, &src->entry->idx.oid))\n+\t\treturn 0;\n+\n \t/* Load data if not already done */\n \tif (!trg->data) {\n \t\tread_lock();\n@@ -2506,6 +2527,9 @@ static void prepare_pack(int window, int depth)\n \tuint32_t i, nr_deltas;\n \tunsigned n;\n \n+\tif (use_delta_islands)\n+\t\tresolve_tree_islands(progress, &to_pack);\n+\n \tget_object_details();\n \n \t/*\n@@ -2669,6 +2693,9 @@ static void show_commit(struct commit *commit, void *data)\n \n \tif (write_bitmap_index)\n \t\tindex_commit_for_bitmap(commit);\n+\n+\tif (use_delta_islands)\n+\t\tpropagate_island_marks(commit);\n }\n \n static void show_object(struct object *obj, const char *name, void *data)\n@@ -2676,6 +2703,19 @@ static void show_object(struct object *obj, const char *name, void *data)\n \tadd_preferred_base_object(name);\n \tadd_object_entry(&obj->oid, obj->type, name, 0);\n \tobj->flags |= OBJECT_ADDED;\n+\n+\tif (use_delta_islands) {\n+\t\tconst char *p;\n+\t\tunsigned depth = 0;\n+\t\tstruct object_entry *ent;\n+\n+\t\tfor (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))\n+\t\t\tdepth++;\n+\n+\t\tent = packlist_find(&to_pack, obj->oid.hash, NULL);\n+\t\tif (ent && depth > ent->tree_depth)\n+\t\t\tent->tree_depth = depth;\n+\t}\n }\n \n static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)\n@@ -3003,6 +3043,9 @@ static void get_object_list(int ac, const char **av)\n \tif (use_bitmap_index && !get_object_list_from_bitmap(&revs))\n \t\treturn;\n \n+\tif (use_delta_islands)\n+\t\tload_delta_islands();\n+\n \tif (prepare_revision_walk(&revs))\n \t\tdie(\"revision walk setup failed\");\n \tmark_edges_uninteresting(&revs, show_edge);\n@@ -3182,6 +3225,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \t\t option_parse_missing_action },\n \t\tOPT_BOOL(0, \"exclude-promisor-objects\", &exclude_promisor_objects,\n \t\t\t N_(\"do not pack objects in promisor packfiles\")),\n+\t\tOPT_BOOL(0, \"delta-islands\", &use_delta_islands,\n+\t\t\t N_(\"enable islands for delta compression\")),\n \t\tOPT_END(),\n \t};\n \n@@ -3308,6 +3353,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (pack_to_stdout || !rev_list_all)\n \t\twrite_bitmap_index = 0;\n \n+\tif (use_delta_islands)\n+\t\targv_array_push(&rp, \"--topo-order\");\n+\n \tif (progress && all_progress_implied)\n \t\tprogress = 2;\n \n-- \n2.18.0.237.gffdb1dbdaa\n\n"},{"id":"353298","messageId":"CACsJy8AzksB=rfaX_dfboMXHjqj6gj+erdF6eRFAKmWA1-3PUg@mail.gmail.com","threadId":"48935","inReplyTo":"20180722054836.28935-3-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-07-22T08:50:56Z","receivedAt":"2018-07-22T08:52:24Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Jul 22, 2018 at 7:51 AM Christian Couder\n wrote:\n> diff --git a/Documentation/config.txt b/Documentation/config.txt\n> index a32172a43c..f682e92a1a 100644\n> --- a/Documentation/config.txt\n> +++ b/Documentation/config.txt\n> @@ -2542,6 +2542,10 @@ Note that changing the compression level will not automatically recompress\n> all existing objects. You can force recompression by passing the -F option\n> to linkgit:git-repack[1].\n>\n> +pack.island::\n> + A regular expression configuring a set of delta islands. See\n> + \"DELTA ISLANDS\" in linkgit:git-pack-objects[1] for details.\n> +\n\nThat section is not added until 3/5 though.\n\n> diff --git a/delta-islands.c b/delta-islands.c\n> new file mode 100644\n> index 0000000000..645fe966c5\n> --- /dev/null\n> +++ b/delta-islands.c\n> @@ -0,0 +1,490 @@\n> +#include \"builtin.h\"\n\nA bit weird that builtin.h would be needed...\n\n> +void resolve_tree_islands(int progress, struct packing_data *to_pack)\n> +{\n> + struct progress *progress_state = NULL;\n> + struct object_entry **todo;\n> + int nr = 0;\n> + int i;\n> +\n> + if (!island_marks)\n> + return;\n> +\n> + /*\n> + * We process only trees, as commits and tags have already been handled\n> + * (and passed their marks on to root trees, as well. We must make sure\n> + * to process them in descending tree-depth order so that marks\n> + * propagate down the tree properly, even if a sub-tree is found in\n> + * multiple parent trees.\n> + */\n> + todo = xmalloc(to_pack->nr_objects * sizeof(*todo));\n> + for (i = 0; i < to_pack->nr_objects; i++) {\n> + if (oe_type(&to_pack->objects[i]) == OBJ_TREE)\n> + todo[nr++] = &to_pack->objects[i];\n> + }\n> + qsort(todo, nr, sizeof(*todo), cmp_tree_depth);\n> +\n> + if (progress)\n> + progress_state = start_progress(\"Propagating island marks\", nr);\n\n_() (same comment for other strings too)\n\n> diff --git a/pack-objects.h b/pack-objects.h\n> index edf74dabdd..8eecd67991 100644\n> --- a/pack-objects.h\n> +++ b/pack-objects.h\n> @@ -100,6 +100,10 @@ struct object_entry {\n> unsigned type_:TYPE_BITS;\n> unsigned no_try_delta:1;\n> unsigned in_pack_type:TYPE_BITS; /* could be delta */\n> +\n> + unsigned int tree_depth; /* should be repositioned for packing? */\n> + unsigned char layer;\n> +\n\nThis looks very much like an optional feature. To avoid increasing\npack-objects memory usage for common case, please move this to struct\npacking_data.\n\n> unsigned preferred_base:1; /*\n> * we do not pack this, but is available\n> * to be used as the base object to delta\n> --\n> 2.18.0.237.gffdb1dbdaa\n-- \nDuy\n"},{"id":"353299","messageId":"CACsJy8CmJt1Wj=e4TNUUxY-Czn+h0BTVAWLY0ujJhgUKC+Y6yw@mail.gmail.com","threadId":"48935","inReplyTo":"20180722054836.28935-4-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-07-22T08:55:51Z","receivedAt":"2018-07-22T08:56:20Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Jul 22, 2018 at 7:52 AM Christian Couder\n wrote:\n> @@ -700,51 +705,58 @@ static struct object_entry **compute_write_order(void)\n> */\n> for_each_tag_ref(mark_tagged, NULL);\n>\n> - /*\n> - * Give the objects in the original recency order until\n> - * we see a tagged tip.\n> - */\n> + if (use_delta_islands)\n> + max_layers = compute_pack_layers(&to_pack);\n> +\n> ALLOC_ARRAY(wo, to_pack.nr_objects);\n> - for (i = wo_end = 0; i < to_pack.nr_objects; i++) {\n> - if (objects[i].tagged)\n> - break;\n> - add_to_write_order(wo, &wo_end, &objects[i]);\n> - }\n> - last_untagged = i;\n> + wo_end = 0;\n>\n> - /*\n> - * Then fill all the tagged tips.\n> - */\n> - for (; i < to_pack.nr_objects; i++) {\n> - if (objects[i].tagged)\n> + for (; write_layer < max_layers; ++write_layer) {\n> + /*\n> + * Give the objects in the original recency order until\n> + * we see a tagged tip.\n> + */\n> + for (i = 0; i < to_pack.nr_objects; i++) {\n> + if (objects[i].tagged)\n> + break;\n> add_to_write_order(wo, &wo_end, &objects[i]);\n> - }\n> + }\n> + last_untagged = i;\n>\n> - /*\n> - * And then all remaining commits and tags.\n> - */\n> - for (i = last_untagged; i < to_pack.nr_objects; i++) {\n> - if (oe_type(&objects[i]) != OBJ_COMMIT &&\n> - oe_type(&objects[i]) != OBJ_TAG)\n> - continue;\n> - add_to_write_order(wo, &wo_end, &objects[i]);\n> - }\n> + /*\n> + * Then fill all the tagged tips.\n> + */\n\nIf we move the code in this loop to a separate function, in a separate\npatch, first, would it produce a better diff? I think all the\nindentation change here makes it a bit hard to read.\n\n> + for (; i < to_pack.nr_objects; i++) {\n> + if (objects[i].tagged)\n> + add_to_write_order(wo, &wo_end, &objects[i]);\n> + }\n-- \nDuy\n"},{"id":"353323","messageId":"CAP8UFD0K+F5D2q5UY-aX9tmtkqvgMiKf=bq+wE+yZuxzyQst_g@mail.gmail.com","threadId":"48935","inReplyTo":"CACsJy8AzksB=rfaX_dfboMXHjqj6gj+erdF6eRFAKmWA1-3PUg@mail.gmail.com","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-07-22T13:57:23Z","receivedAt":"2018-07-22T13:57:27Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sun, Jul 22, 2018 at 10:50 AM, Duy Nguyen wrote:\n> On Sun, Jul 22, 2018 at 7:51 AM Christian Couder\n> wrote:\n\n>> +pack.island::\n>> + A regular expression configuring a set of delta islands. See\n>> + \"DELTA ISLANDS\" in linkgit:git-pack-objects[1] for details.\n>> +\n>\n> That section is not added until 3/5 though.\n\nYeah, so I guess it is better to move this hunk to 3/5 and keep\npack.island undocumented until the delta islands code is actually used\nby pack-objects.\n\n>> diff --git a/delta-islands.c b/delta-islands.c\n>> new file mode 100644\n>> index 0000000000..645fe966c5\n>> --- /dev/null\n>> +++ b/delta-islands.c\n>> @@ -0,0 +1,490 @@\n>> +#include \"builtin.h\"\n>\n> A bit weird that builtin.h would be needed...\n\nYeah, I will get rid of that include in the next iteration.\n\n>> + if (progress)\n>> + progress_state = start_progress(\"Propagating island marks\", nr);\n>\n> _() (same comment for other strings too)\n\nOk, the strings will be marked for translation in the next iteration.\n\n>> diff --git a/pack-objects.h b/pack-objects.h\n>> index edf74dabdd..8eecd67991 100644\n>> --- a/pack-objects.h\n>> +++ b/pack-objects.h\n>> @@ -100,6 +100,10 @@ struct object_entry {\n>> unsigned type_:TYPE_BITS;\n>> unsigned no_try_delta:1;\n>> unsigned in_pack_type:TYPE_BITS; /* could be delta */\n>> +\n>> + unsigned int tree_depth; /* should be repositioned for packing? */\n>> + unsigned char layer;\n>> +\n>\n> This looks very much like an optional feature. To avoid increasing\n> pack-objects memory usage for common case, please move this to struct\n> packing_data.\n\nOk, I will take a look at that.\n\nThanks for the review,\nChristian.\n"},{"id":"353398","messageId":"CAGZ79kbF7g3E4hBa0VqMqBoovbAb2dHaGFNRL=+f7Lce1AduVg@mail.gmail.com","threadId":"48935","inReplyTo":"20180722054836.28935-4-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-23T18:52:49Z","receivedAt":"2018-07-23T18:53:04Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sat, Jul 21, 2018 at 10:49 PM Christian Couder\n wrote:\n>\n> From: Jeff King \n>\n> Implement support for delta islands in git pack-objects\n> and document how delta islands work in\n> \"Documentation/git-pack-objects.txt\".\n>\n> Signed-off-by: Jeff King \n> Signed-off-by: Christian Couder \n> ---\n> Documentation/git-pack-objects.txt | 88 +++++++++++++++++++\n> builtin/pack-objects.c | 130 ++++++++++++++++++++---------\n> 2 files changed, 177 insertions(+), 41 deletions(-)\n>\n> diff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt\n> index d95b472d16..7b7a36056f 100644\n> --- a/Documentation/git-pack-objects.txt\n> +++ b/Documentation/git-pack-objects.txt\n> @@ -289,6 +289,94 @@ Unexpected missing object will raise an error.\n> --unpack-unreachable::\n> Keep unreachable objects in loose form. This implies `--revs`.\n>\n> +--delta-islands::\n> + Restrict delta matches based on \"islands\". See DELTA ISLANDS\n> + below.\n> +\n> +\n> +DELTA ISLANDS\n> +-------------\n> +\n> +When possible, `pack-objects` tries to reuse existing on-disk deltas to\n> +avoid having to search for new ones on the fly. This is an important\n> +optimization for serving fetches, because it means the server can avoid\n> +inflating most objects at all and just send the bytes directly from\n> +disk. This optimization can't work when an object is stored as a delta\n> +against a base which the receiver does not have (and which we are not\n> +already sending). In that case the server \"breaks\" the delta and has to\n> +find a new one, which has a high CPU cost. Therefore it's important for\n> +performance that the set of objects in on-disk delta relationships match\n> +what a client would fetch.\n> +\n> +In a normal repository, this tends to work automatically. The objects\n> +are mostly reachable from the branches and tags, and that's what clients\n> +fetch. Any deltas we find on the server are likely to be between objects\n> +the client has or will have.\n> +\n> +But in some repository setups, you may have several related but separate\n> +groups of ref tips, with clients tending to fetch those groups\n> +independently. For example, imagine that you are hosting several \"forks\"\n> +of a repository in a single shared object store, and letting clients\n> +view them as separate repositories through `GIT_NAMESPACE` or separate\n> +repos using the alternates mechanism. A naive repack may find that the\n> +optimal delta for an object is against a base that is only found in\n> +another fork. But when a client fetches, they will not have the base\n> +object, and we'll have to find a new delta on the fly.\n> +\n> +A similar situation may exist if you have many refs outside of\n> +`refs/heads/` and `refs/tags/` that point to related objects (e.g.,\n> +`refs/pull` or `refs/changes` used by some hosting providers). By\n> +default, clients fetch only heads and tags, and deltas against objects\n> +found only in those other groups cannot be sent as-is.\n> +\n> +Delta islands solve this problem by allowing you to group your refs into\n> +distinct \"islands\". Pack-objects computes which objects are reachable\n> +from which islands, and refuses to make a delta from an object `A`\n> +against a base which is not present in all of `A`'s islands. This\n> +results in slightly larger packs (because we miss some delta\n> +opportunities), but guarantees that a fetch of one island will not have\n> +to recompute deltas on the fly due to crossing island boundaries.\n> +\n> +Islands are configured via the `pack.island` option, which can be\n> +specified multiple times. Each value is a left-anchored regular\n> +expressions matching refnames. For example:\n> +\n> +-------------------------------------------\n> +[pack]\n> +island = refs/heads/\n> +island = refs/tags/\n> +-------------------------------------------\n> +\n> +puts heads and tags into an island (whose name is the empty string; see\n> +below for more on naming). Any refs which do not match those regular\n> +expressions (e.g., `refs/pull/123`) is not in any island. Any object\n> +which is reachable only from `refs/pull/` (but not heads or tags) is\n> +therefore not a candidate to be used as a base for `refs/heads/`.\n> +\n> +Refs are grouped into islands based on their \"names\", and two regexes\n> +that produce the same name are considered to be in the same island. The\n> +names are computed from the regexes by concatenating any capture groups\n> +from the regex (and if there are none, then the name is the empty\n> +string, as in the above example). This allows you to create arbitrary\n> +numbers of islands. For example, imagine you store the refs for each\n> +fork in `refs/virtual/ID`, where `ID` is a numeric identifier. You might\n> +then configure:\n> +\n> +-------------------------------------------\n> +[pack]\n> +island = refs/virtual/([0-9]+)/heads/\n> +island = refs/virtual/([0-9]+)/tags/\n> +island = refs/virtual/([0-9]+)/(pull)/\n> +-------------------------------------------\n> +\n> +That puts the heads and tags for each fork in their own island (named\n> +\"1234\" or similar), and the pull refs for each go into their own\n> +\"1234-pull\".\n> +\n> +Note that we pick a single island for each regex to go into, using \"last\n> +one wins\" ordering (which allows repo-specific config to take precedence\n> +over user-wide config, and so forth).\n\nI had to read all of this [background information] to understand the\nconcept and I think it is misnamed, as my gut instinct first told me\nto have deltas only \"within an island and no island hopping is allowed\".\n(This message reads a bit like a commit message, not as documentation\nas it is long winded, too).\n\nThis feature makes sure that the \"common foundation\" base is packed\nin a way that it is not borrowing construction pieces from any of\nthe different things atop the common foundation.\nIt really is about packing the base, but naming it related to the\nislands, that are on top of the common sea bed led me to think\nthat the islands are important of this feature, but really it is about\nmaking the sea bed easy to use and not tied to one of the islands?\n\nWhat about renaming this feature to\n\n[pack]\n excludePartialReach = refs/virtual/[0-9]]+/tags/\n\n \"By setting `pack.excludePartialReach`, object deltafication is\n prohibited for objects that are not reachable from all\n manifestations of the given regex\"\n\nCryptic, but it explains it in my mind in a shorter, more concise way. ;-)\n\n\n> @@ -3182,6 +3225,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n> option_parse_missing_action },\n> OPT_BOOL(0, \"exclude-promisor-objects\", &exclude_promisor_objects,\n> N_(\"do not pack objects in promisor packfiles\")),\n> + OPT_BOOL(0, \"delta-islands\", &use_delta_islands,\n> + N_(\"enable islands for delta compression\")),\n\nWe enable this feature, but we disallow certain patterns to be used in packing,\nso it sounds weird to me as we tell Git to *not* explore the full design space,\nso we're not enabling it, but rather restricting it?\n"},{"id":"353453","messageId":"20180724095843.GB3578@sigill.intra.peff.net","threadId":"48935","inReplyTo":"CAGZ79kbF7g3E4hBa0VqMqBoovbAb2dHaGFNRL=+f7Lce1AduVg@mail.gmail.com","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-24T09:58:43Z","receivedAt":"2018-07-24T09:58:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 23, 2018 at 11:52:49AM -0700, Stefan Beller wrote:\n\n> > +DELTA ISLANDS\n> > +-------------\n> [...]\n> \n> I had to read all of this [background information] to understand the\n> concept and I think it is misnamed, as my gut instinct first told me\n> to have deltas only \"within an island and no island hopping is allowed\".\n> (This message reads a bit like a commit message, not as documentation\n> as it is long winded, too).\n\nI'm not sure if I'm parsing your sentence correctly, but the reason I\ncalled them \"islands\" is exactly that you'd have deltas within an island\nand want to forbid island hopping. So I wasn't sure if you were saying\n\"that's what I think, but not how the feature works\".\n\nThere _is_ a tricky thing, which is that a given object is going to\nappear in many islands. So the rule is really \"you cannot hop to a base\nthat is not in all of your islands\".\n\n> What about renaming this feature to\n> \n> [pack]\n> excludePartialReach = refs/virtual/[0-9]]+/tags/\n> \n> \"By setting `pack.excludePartialReach`, object deltafication is\n> prohibited for objects that are not reachable from all\n> manifestations of the given regex\"\n> \n> Cryptic, but it explains it in my mind in a shorter, more concise way. ;-)\n\nSo I'm hopelessly biased at this point, having developed and worked with\nthe feature under the \"island\" name for several years. But I find your\nname and explanation pretty confusing. :)\n\nWorse, though, it does not have any noun to refer to the reachable set.\nThe regex capture and the island names are an important part of the\nfeature, because it lets you make a single island out of:\n\n refs/virtual/([0-9]+)/heads\n refs/virtual/([0-9]+)/tags\n\nbut exclude:\n\n refs/virtual/([0-9]+)/(foo)\n\nwhich goes into its own island (\"123-foo\" instead of \"123\"). So what's\nthe equivalent nomenclature to \"island name\"?\n\n> > @@ -3182,6 +3225,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n> > option_parse_missing_action },\n> > OPT_BOOL(0, \"exclude-promisor-objects\", &exclude_promisor_objects,\n> > N_(\"do not pack objects in promisor packfiles\")),\n> > + OPT_BOOL(0, \"delta-islands\", &use_delta_islands,\n> > + N_(\"enable islands for delta compression\")),\n> \n> We enable this feature, but we disallow certain patterns to be used in packing,\n> so it sounds weird to me as we tell Git to *not* explore the full design space,\n> so we're not enabling it, but rather restricting it?\n\nYeah, perhaps \"respect islands during delta compression\" makes more sense.\n\n-Peff\n"},{"id":"353454","messageId":"20180724101627.GC3578@sigill.intra.peff.net","threadId":"48935","inReplyTo":"20180722054836.28935-1-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 0/5] Add delta islands support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-24T10:16:28Z","receivedAt":"2018-07-24T10:16:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 22, 2018 at 07:48:31AM +0200, Christian Couder wrote:\n\n> I kept Peff as the author and took the liberty to add his\n> Signed-off-by to all the patches.\n\nYes, that's fine. This is a topic I've been meaning to upstream for a\nlong time, so I'm happy to see it progressing in that direction.\n\nA few reasons I've been hesitant:\n\n - this produces worse packs for people cloning. The packs we serve at\n GitHub for heavily-forked repositories can be significantly larger\n than what you could get by repacking in isolation.\n\n I think this is inherent in the scheme (we're losing some delta\n opportunities). But I think it's also made worse because the delta\n window gets clogged with candidates that are forbidden by the island\n config. Repacking with a big --window helps (and doesn't take as long\n as it otherwise might because we can reject some object pairs based\n on islands before doing any computation on the content).\n\n I also haven't done much modeling on how this scheme progresses over\n time. Imagine users tend to create forks at random points in time and\n then let them get stale. You're going to accumulate a bunch of\n islands that increasingly don't overlap with each other. And as time\n goes on, your delta opportunities get worse and worse.\n\n Which isn't to say the scheme doesn't work to some degree. It has\n been running in production at GitHub for several years. But it's very\n cobbled together, and I had always hoped to give it some more careful\n thought before sending it upstream. ;) That may be \"the perfect is\n the enemy of the good\" though (or at least the enemy of the\n mediocre).\n\n - the whole regex island-naming configuration feels complicated and\n hacky to me. I haven't been able to come up with a better solution,\n though.\n\n - the whole islandCore thing is it's own weirdness (more below)\n\n> The patches look good to me except perhaps that \"pack.islandCore\" is\n> not documented. Maybe something could be added in\n> Documentation/technical/ too, or maybe improving commit messages could\n> be enough.\n\nSo basically what islandCore does is make one island \"special\", and we\nwrite all of its objects out first in the packfile. The idea here was\nthat it would interact well with the pack-reuse code which tries to send\nthe early part of the pack out verbatim. And if you could pick the fork\nwhich is most-often cloned, then that would be a win (so you'd pick\ntorvalds/linux.git here).\n\nBut:\n\n - the pack-reuse code we have upstream is crap; it doesn't kick in for\n this instance anyway, because it's too concerned with whether you're\n sending all of the pack. So if you have a 10GB pack and the \"core\"\n island is the entire first 1GB, you should be able to ship out that\n first GB easily. But the code says \"well, that's only 10%!\", which is\n not enough to trigger.\n\n I have replacement code (which we have been running in production)\n that is more clever about the threshold, and also can handle gaps in\n the continuity (so we might realize we need to send objects 1-5000,\n then skip a few, then 5037-8000, and so on). And after that, it's not\n at all clear to me if the islandCore thing is actually still helpful.\n\n - it's hard to configure, because it may actually change over time\n (whereas all the other island config is basically static and just impacts\n how we consider the refs that are there)\n\n - there may actually be _multiple_ forks that are \"special\". In\n torvalds/linux, for example, there's a fair bit of hierarchy, and\n there are people who forked Linus and have their own active\n sub-community. The actual island concept handles this kind of\n layering OK, but the islandCore thing is pretty static.\n\nSo I'm not sure if islandCore is even needed or not. But somebody would\nhave to do some experiments to figure it out (and obviously I should\nshare the replacement pack-reuse patches).\n\n-Peff\n"},{"id":"353455","messageId":"20180724102421.GD3578@sigill.intra.peff.net","threadId":"48935","inReplyTo":"20180722054836.28935-6-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 5/5] t: add t9930-delta-islands.sh","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-24T10:24:21Z","receivedAt":"2018-07-24T10:24:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 22, 2018 at 07:48:36AM +0200, Christian Couder wrote:\n\n> From: Jeff King \n> \n> Signed-off-by: Jeff King \n> Signed-off-by: Christian Couder \n> ---\n> t/t9930-delta-islands.sh | 143 +++++++++++++++++++++++++++++++++++++++\n\nFor topics that I'm not immediately sending upstream, I usually stick\nthem in the t99xx range, so they don't conflict with upstream tests. But\nfor upstream, this should probably be in the t53xx range.\n\n-Peff\n"},{"id":"353469","messageId":"xmqqy3e0zjw0.fsf@gitster-ct.c.googlers.com","threadId":"48935","inReplyTo":"20180722054836.28935-2-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 1/5] packfile: make get_delta_base() non static","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-07-24T16:19:27Z","receivedAt":"2018-07-24T16:19:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> From: Jeff King \n>\n> As get_delta_base() will be used outside 'packfile.c' in\n> a following commit, let's make it non static and let's\n> declare it in 'packfile.h'.\n\nAs a public function in *.h, don't we want a bit of comment there to\nhelp those who want to use it from outside packfile.c?\n\n\n> Signed-off-by: Jeff King \n> Signed-off-by: Christian Couder \n> ---\n> packfile.c | 10 +++++-----\n> packfile.h | 3 +++\n> 2 files changed, 8 insertions(+), 5 deletions(-)\n>\n> diff --git a/packfile.c b/packfile.c\n> index 7cd45aa4b2..4646bff5ff 100644\n> --- a/packfile.c\n> +++ b/packfile.c\n> @@ -1037,11 +1037,11 @@ const struct packed_git *has_packed_and_bad(const unsigned char *sha1)\n> \treturn NULL;\n> }\n> \n> -static off_t get_delta_base(struct packed_git *p,\n> -\t\t\t\t struct pack_window **w_curs,\n> -\t\t\t\t off_t *curpos,\n> -\t\t\t\t enum object_type type,\n> -\t\t\t\t off_t delta_obj_offset)\n> +off_t get_delta_base(struct packed_git *p,\n> +\t\t struct pack_window **w_curs,\n> +\t\t off_t *curpos,\n> +\t\t enum object_type type,\n> +\t\t off_t delta_obj_offset)\n> {\n> \tunsigned char *base_info = use_pack(p, w_curs, *curpos, NULL);\n> \toff_t base_offset;\n> diff --git a/packfile.h b/packfile.h\n> index cc7eaffe1b..30f0811382 100644\n> --- a/packfile.h\n> +++ b/packfile.h\n> @@ -125,6 +125,9 @@ extern void *unpack_entry(struct repository *r, struct packed_git *, off_t, enum\n> extern unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\n> extern unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);\n> extern int unpack_object_header(struct packed_git *, struct pack_window **, off_t *, unsigned long *);\n> +extern off_t get_delta_base(struct packed_git *p, struct pack_window **w_curs,\n> +\t\t\t off_t *curpos, enum object_type type,\n> +\t\t\t off_t delta_obj_offset);\n> \n> extern void release_pack_memory(size_t);\n"},{"id":"353491","messageId":"xmqqpnzczila.fsf@gitster-ct.c.googlers.com","threadId":"48935","inReplyTo":"20180722054836.28935-3-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-07-24T16:47:29Z","receivedAt":"2018-07-24T16:47:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> From: Jeff King \n>\n> Hosting providers that allow users to \"fork\" existing\n> repos want as much as possible those forks to use a\n> small amount of disk space.\n\n\"... want those forks to consume as little amount of disk space as\npossible?\" Or perhaps \"... want those forks to share as much disk\nspace as possible\"?\n\n> Using alternates to keep all the objects from all the forks into a\n> unique central repo is way to do that, but ...\n\ns/is way to/is a way to/, I guess, but that makes it sound as if the\nseries invented a way to share objects without using alternates.\n\n> it can have some\n> drawbacks. Especially when packing the central repo, deltas will\n> be created between objects from different forks.\n>\n> This can make cloning or fetching a fork much slower and much more\n> CPU intensive as Git might have to compute new deltas for many\n> objects to avoid sending objects from a different fork.\n>\n> Delta islands is a way to store objects from different forks in\n> the same repo and packfile without having deltas between objects\n> from different forks.\n\nI think another paragraph between the above two is needed to briefly\noutline the central idea (which would make it clear why that is\ncalled \"delta islands\") is called for. Perhaps\n\n\tBecause the inefficiency primarily arises when an object is\n\tdelitified against another object that does not exist in the\n\tsame fork, we partion objects into sets that appear in the\n\tsame fork, and define \"delta islands\". When finding delta\n\tbase, we do not allow an object outside the same island to\n\tbe considered as its base.\n\nor something along that line. Perhaps that would even make the last\nparagraph unnecessary.\n\n> +struct island_bitmap {\n> +\tuint32_t refcount;\n> +\tuint32_t bits[];\n> +};\n> +\n> +static uint32_t island_bitmap_size;\n> +\n> +/*\n> + * Allocate a new bitmap; if \"old\" is not NULL, the new bitmap will be a copy\n> + * of \"old\". Otherwise, the new bitmap is empty.\n> + */\n> +static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old)\n> +{\n> +\tsize_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4);\n> +\tstruct island_bitmap *b = xcalloc(1, size);\n\nIs one of the variants of flex array macros applicable here?\n\n> +\tif (old)\n> +\t\tmemcpy(b, old, size);\n> +\n> +\tb->refcount = 1;\n> +\treturn b;\n> +}\n> +\n> +static void island_bitmap_or(struct island_bitmap *a, const struct island_bitmap *b)\n> +{\n> +\tuint32_t i;\n> +\n> +\tfor (i = 0; i < island_bitmap_size; ++i)\n> +\t\ta->bits[i] |= b->bits[i];\n> +}\n> +\n> +static int island_bitmap_is_subset(struct island_bitmap *self,\n> +\t\tstruct island_bitmap *super)\n> +{\n> +\tuint32_t i;\n> +\n> +\tif (self == super)\n> +\t\treturn 1;\n> +\n> +\tfor (i = 0; i < island_bitmap_size; ++i) {\n> +\t\tif ((self->bits[i] & super->bits[i]) != self->bits[i])\n> +\t\t\treturn 0;\n> +\t}\n> +\n> +\treturn 1;\n> +}\n> +#define ISLAND_BITMAP_BLOCK(x) (x / 32)\n> +#define ISLAND_BITMAP_MASK(x) (1 << (x % 32))\n> +\n> +static void island_bitmap_set(struct island_bitmap *self, uint32_t i)\n> +{\n> +\tself->bits[ISLAND_BITMAP_BLOCK(i)] |= ISLAND_BITMAP_MASK(i);\n> +}\n> +\n> +static int island_bitmap_get(struct island_bitmap *self, uint32_t i)\n> +{\n> +\treturn (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0;\n> +}\n> +\n\nNot necessarily a complaint, but do we need another implementation\nof bitmap here, or the compressed bitmap used for the pack bitmap is\nunsuited for the purpose of this thing (e.g. perhaps it is overkill,\nas we won't be shooting for saving disk footprint of a bitmap that\nwe are not going to save on disk anyway)?\n\n> +static int cmp_tree_depth(const void *va, const void *vb)\n> +{\n> +\tstruct object_entry *a = *(struct object_entry **)va;\n> +\tstruct object_entry *b = *(struct object_entry **)vb;\n> +\treturn a->tree_depth - b->tree_depth;\n> +}\n> +\n> +void resolve_tree_islands(int progress, struct packing_data *to_pack)\n> +{\n> +\tstruct progress *progress_state = NULL;\n> +\tstruct object_entry **todo;\n> +\tint nr = 0;\n> +\tint i;\n> +\n> +\tif (!island_marks)\n> +\t\treturn;\n> +\n> +\t/*\n> +\t * We process only trees, as commits and tags have already been handled\n> +\t * (and passed their marks on to root trees, as well. We must make sure\n> +\t * to process them in descending tree-depth order so that marks\n> +\t * propagate down the tree properly, even if a sub-tree is found in\n> +\t * multiple parent trees.\n> +\t */\n> +\ttodo = xmalloc(to_pack->nr_objects * sizeof(*todo));\n> +\tfor (i = 0; i < to_pack->nr_objects; i++) {\n> +\t\tif (oe_type(&to_pack->objects[i]) == OBJ_TREE)\n> +\t\t\ttodo[nr++] = &to_pack->objects[i];\n> +\t}\n> +\tqsort(todo, nr, sizeof(*todo), cmp_tree_depth);\n\nHmph, at this stage nobody actually seems to set tree_depth; I am\nwondering how a tree that is at the root in one commit but appears\nas a subdirectory in another commit is handled by this code.\n\n> +static regex_t *island_regexes;\n> +static unsigned int island_regexes_alloc, island_regexes_nr;\n> +static const char *core_island_name;\n\nAre these (and the bitmap & hashtable) something that \"everything in\nthe_repository\" folks would come in and nuke as global variables? I\nhaven't thought deeply about it, but these smell like that there\nwould be one set of such in-core variables per one in-core object\nstore plus refs (i.e. repository instance).\n\n"},{"id":"353492","messageId":"xmqqk1pkzhuo.fsf@gitster-ct.c.googlers.com","threadId":"48935","inReplyTo":"20180722054836.28935-4-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-07-24T17:03:27Z","receivedAt":"2018-07-24T17:03:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> +Islands are configured via the `pack.island` option, which can be\n> +specified multiple times. Each value is a left-anchored regular\n> +expressions matching refnames. For example:\n> +\n> +-------------------------------------------\n> +[pack]\n> +island = refs/heads/\n> +island = refs/tags/\n> +-------------------------------------------\n> +\n> +puts heads and tags into an island (whose name is the empty string; see\n> +below for more on naming). Any refs which do not match those regular\n> +expressions (e.g., `refs/pull/123`) is not in any island. Any object\n> +which is reachable only from `refs/pull/` (but not heads or tags) is\n> +therefore not a candidate to be used as a base for `refs/heads/`.\n> +\n> +Refs are grouped into islands based on their \"names\", and two regexes\n> +that produce the same name are considered to be in the same island. The\n> +names are computed from the regexes by concatenating any capture groups\n> +from the regex (and if there are none, then the name is the empty\n> +string, as in the above example). This allows you to create arbitrary\n> +numbers of islands. For example, imagine you store the refs for each\n> +fork in `refs/virtual/ID`, where `ID` is a numeric identifier. You might\n> +then configure:\n> +\n> +-------------------------------------------\n> +[pack]\n> +island = refs/virtual/([0-9]+)/heads/\n> +island = refs/virtual/([0-9]+)/tags/\n> +island = refs/virtual/([0-9]+)/(pull)/\n> +-------------------------------------------\n\nIt becomes clear only from this example that what the feature calls\n(and documented in patch 2/5) \"regexp\" is not BRE but ERE. Update\n2/5 so that it is clear to readers of \"git config --help\" who looks\nfor \"pack.island\" in the output.\n\n> +That puts the heads and tags for each fork in their own island (named\n> +\"1234\" or similar), and the pull refs for each go into their own\n> +\"1234-pull\".\n\n\"by concatenating any capture groups\" made me imagine that the last\none would be \"1234pull\" without dash. The actual rule should be\nmentioned in that paragraph (i.e. \"concatenating any capture groups\nfrom the regex, with a '-' dash in between\" or something like that).\n\n> +Note that we pick a single island for each regex to go into, using \"last\n> +one wins\" ordering (which allows repo-specific config to take precedence\n> +over user-wide config, and so forth).\n"},{"id":"353493","messageId":"xmqqfu08zhh7.fsf@gitster-ct.c.googlers.com","threadId":"48935","inReplyTo":"xmqqk1pkzhuo.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-07-24T17:11:32Z","receivedAt":"2018-07-24T17:11:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n>> +-------------------------------------------\n>> +[pack]\n>> +island = refs/virtual/([0-9]+)/heads/\n>> +island = refs/virtual/([0-9]+)/tags/\n>> +island = refs/virtual/([0-9]+)/(pull)/\n>> +-------------------------------------------\n>\n> It becomes clear only from this example that what the feature calls\n> (and documented in patch 2/5) \"regexp\" is not BRE but ERE. Update\n> 2/5 so that it is clear to readers of \"git config --help\" who looks\n> for \"pack.island\" in the output.\n>\n>> +That puts the heads and tags for each fork in their own island (named\n>> +\"1234\" or similar), and the pull refs for each go into their own\n>> +\"1234-pull\".\n>\n> \"by concatenating any capture groups\" made me imagine that the last\n> one would be \"1234pull\" without dash. The actual rule should be\n> mentioned in that paragraph (i.e. \"concatenating any capture groups\n> from the regex, with a '-' dash in between\" or something like that).\n\nAnother thing I noticed from 2/5 is that you can have up to 7 such\ncapture groups. I do not have any opinion if 7 is too few or too\nmany, but we would want the number to be documented, and end-user\ninput diagnosed when it requires more captures than we support (if\nwe are not already checking, that is).\n"},{"id":"353495","messageId":"xmqqa7qgzh6c.fsf@gitster-ct.c.googlers.com","threadId":"48935","inReplyTo":"20180724101627.GC3578@sigill.intra.peff.net","subject":"Re: [RFC PATCH 0/5] Add delta islands support","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2018-07-24T17:18:03Z","receivedAt":"2018-07-24T17:18:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I think this is inherent in the scheme (we're losing some delta\n> opportunities). But I think it's also made worse because the delta\n> window gets clogged with candidates that are forbidden by the island\n> config.\n\nHmph, and the reason why objects that do not even belong to the same\nisland to be usable as a base are in the object list in the first\nplace is...?\n\n> Repacking with a big --window helps (and doesn't take as long\n> as it otherwise might because we can reject some object pairs based\n> on islands before doing any computation on the content).\n\nAh, then yes, a large window with early culling based on the delta\nisland criteria definitely sounds like the right solution to that\nproblem.\n\n> I have replacement code (which we have been running in production)\n> that is more clever about the threshold, and also can handle gaps in\n> the continuity (so we might realize we need to send objects 1-5000,\n> then skip a few, then 5037-8000, and so on).\n\nThat vaguely sounds similar to what folks at $DAYJOB runs in their\nGerrit/jgit thing.\n\n"},{"id":"353496","messageId":"CAGZ79kZkagveB+jG9iLQ2ohaSfAzY5YtWC=BTdD1o9OQUrw90Q@mail.gmail.com","threadId":"48935","inReplyTo":"20180724095843.GB3578@sigill.intra.peff.net","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-24T17:20:05Z","receivedAt":"2018-07-24T17:20:20Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Jul 24, 2018 at 2:58 AM Jeff King wrote:\n>\n> On Mon, Jul 23, 2018 at 11:52:49AM -0700, Stefan Beller wrote:\n>\n> > > +DELTA ISLANDS\n> > > +-------------\n> > [...]\n> >\n> > I had to read all of this [background information] to understand the\n> > concept and I think it is misnamed, as my gut instinct first told me\n> > to have deltas only \"within an island and no island hopping is allowed\".\n> > (This message reads a bit like a commit message, not as documentation\n> > as it is long winded, too).\n>\n> I'm not sure if I'm parsing your sentence correctly, but the reason I\n> called them \"islands\" is exactly that you'd have deltas within an island\n> and want to forbid island hopping. So I wasn't sure if you were saying\n> \"that's what I think, but not how the feature works\".\n\nYeah, you want to avoid island hopping, but still want the sea bed to be\nuseful for all islands (i.e. to have the largest possible base pack, that all\nislands can share without being overexposed with objects they should\nnot see). And that is the main feature IMHO. It is not so much about\nisland separation (as you could use its own physically separated repo\nfor these separation tasks), but the main selling point of this feature\nis that it enables a base pack that can be shared across all islands\nwithout violating ACLs for example or making one island \"too big\"\n(having unneeded objects on the island).\n\nSo metaphorically speaking I assumed the sea bed to support\nall islands, which themselves are independent from each other.\n\n> There _is_ a tricky thing, which is that a given object is going to\n> appear in many islands. So the rule is really \"you cannot hop to a base\n> that is not in all of your islands\".\n\nYes, if islands were numbers, we'd be looking for the Greatest common\ncommon divisor for all of them, as all islands have to have access to\nall objects in the base pack.\n\n>\n> > What about renaming this feature to\n> >\n> > [pack]\n> > excludePartialReach = refs/virtual/[0-9]]+/tags/\n> >\n> > \"By setting `pack.excludePartialReach`, object deltafication is\n> > prohibited for objects that are not reachable from all\n> > manifestations of the given regex\"\n> >\n> > Cryptic, but it explains it in my mind in a shorter, more concise way. ;-)\n>\n> So I'm hopelessly biased at this point, having developed and worked with\n> the feature under the \"island\" name for several years. But I find your\n> name and explanation pretty confusing. :)\n\nOk.\n\n>\n> Worse, though, it does not have any noun to refer to the reachable set.\n> The regex capture and the island names are an important part of the\n> feature, because it lets you make a single island out of:\n>\n> refs/virtual/([0-9]+)/heads\n> refs/virtual/([0-9]+)/tags\n>\n> but exclude:\n>\n> refs/virtual/([0-9]+)/(foo)\n>\n> which goes into its own island (\"123-foo\" instead of \"123\"). So what's\n> the equivalent nomenclature to \"island name\"?\n\nSo in my understanding we have a \"common base pack\" and specific\npacks on top for each \"island\".\n\nRegarding naming I find islands interesting and well fitting here, I don't\nknow of any better name.\n\nI was just confused in the beginning as the name indicates that we care\nabout the islands, but we rather care about *not* hopping them.\n\nDo you envision to have \"groups of islands\" (an atoll) for say all\nopen source clones of linux.git, such that you can layer the packs?\nYou would not just have the base pack + island pack, but have one\npack that is common to most islands?\n\nSorry if the initial email came off as a rant; I think the islands\nmetaphor is very good.\n\nThanks,\nStefan\n"},{"id":"353530","messageId":"20180724211455.GA17803@sigill.intra.peff.net","threadId":"48935","inReplyTo":"xmqqa7qgzh6c.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 0/5] Add delta islands support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-24T21:14:56Z","receivedAt":"2018-07-24T21:14:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 24, 2018 at 10:18:03AM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > I think this is inherent in the scheme (we're losing some delta\n> > opportunities). But I think it's also made worse because the delta\n> > window gets clogged with candidates that are forbidden by the island\n> > config.\n> \n> Hmph, and the reason why objects that do not even belong to the same\n> island to be usable as a base are in the object list in the first\n> place is...?\n\nBecause we are doing a \"git repack -ad\" here. So we are considering\n_all_ of the objects, but avoiding making deltas between some of them.\n\nDuring an actual fetch, the islands are not used at all (but the delta\nrelationships left on disk are important for letting us reuse those\ndeltas as-is).\n\n> > Repacking with a big --window helps (and doesn't take as long\n> > as it otherwise might because we can reject some object pairs based\n> > on islands before doing any computation on the content).\n> \n> Ah, then yes, a large window with early culling based on the delta\n> island criteria definitely sounds like the right solution to that\n> problem.\n\nI try to account for this somewhat by looking at islands in the sort we\ndo of the delta candidates. But to be honest, I am not sure how much\nsense that makes (but I did verify experimentally that it helps). Again,\nthis is one of the reasons I had not sent this previously: I am not at\nall confident that it is doing the right thing in all places.\n\n-Peff\n"},{"id":"353641","messageId":"nycvar.QRO.7.76.6.1807261533350.71@tvgsbejvaqbjf.bet","threadId":"48935","inReplyTo":"20180722054836.28935-1-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 0/5] Add delta islands support","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-07-26T13:34:15Z","receivedAt":"2018-07-26T13:34:30Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Chris,\n\n\nOn Sun, 22 Jul 2018, Christian Couder wrote:\n\n> This patch series is upstreaming work made by GitHub and available in:\n> \n> https://github.com/peff/git/commits/jk/delta-islands\n> \n> The patch in the above branch has been split into 5 patches with their\n> own new commit message, but no other change has been made.\n> \n> I kept Peff as the author and took the liberty to add his\n> Signed-off-by to all the patches.\n> \n> The patches look good to me except perhaps that \"pack.islandCore\" is\n> not documented. Maybe something could be added in\n> Documentation/technical/ too, or maybe improving commit messages could\n> be enough.\n> \n> Anyway I wanted to send this nearly \"as is\" first to get early\n> feedback about what should be done.\n> \n> This patch series is also available on GitHub in:\n> \n> https://github.com/chriscool/git/commits/delta-islands\n\nIt might make sense to explain *somewhere* in the cover letter what the\npatches are all about, i.e. what problem they are supposed to solve. I did\nnot see any indication here.\n\nCiao,\nDscho\n\n> \n> Jeff King (5):\n> packfile: make get_delta_base() non static\n> Add delta-islands.{c,h}\n> pack-objects: add delta-islands support\n> repack: add delta-islands support\n> t: add t9930-delta-islands.sh\n> \n> Documentation/config.txt | 8 +\n> Documentation/git-pack-objects.txt | 88 ++++++\n> Documentation/git-repack.txt | 5 +\n> Makefile | 1 +\n> builtin/pack-objects.c | 130 +++++---\n> builtin/repack.c | 9 +\n> delta-islands.c | 490 +++++++++++++++++++++++++++++\n> delta-islands.h | 11 +\n> pack-objects.h | 4 +\n> packfile.c | 10 +-\n> packfile.h | 3 +\n> t/t9930-delta-islands.sh | 143 +++++++++\n> 12 files changed, 856 insertions(+), 46 deletions(-)\n> create mode 100644 delta-islands.c\n> create mode 100644 delta-islands.h\n> create mode 100755 t/t9930-delta-islands.sh\n> \n> -- \n> 2.18.0.237.gffdb1dbdaa\n> \n> \n"},{"id":"353692","messageId":"20180727094026.GA17155@sigill.intra.peff.net","threadId":"48935","inReplyTo":"20180722054836.28935-3-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-27T09:40:26Z","receivedAt":"2018-07-27T09:40:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Jul 22, 2018 at 07:48:33AM +0200, Christian Couder wrote:\n\n> +\t/*\n> +\t * We process only trees, as commits and tags have already been handled\n> +\t * (and passed their marks on to root trees, as well. We must make sure\n> +\t * to process them in descending tree-depth order so that marks\n> +\t * propagate down the tree properly, even if a sub-tree is found in\n> +\t * multiple parent trees.\n> +\t */\n> +\ttodo = xmalloc(to_pack->nr_objects * sizeof(*todo));\n\nI was fiddling with \"make coccicheck\", and it looks like this code could\nstand some modernization. This could use ALLOC_ARRAY().\n\n> +\tfor (i = 0; i < to_pack->nr_objects; i++) {\n> +\t\tif (oe_type(&to_pack->objects[i]) == OBJ_TREE)\n> +\t\t\ttodo[nr++] = &to_pack->objects[i];\n> +\t}\n> +\tqsort(todo, nr, sizeof(*todo), cmp_tree_depth);\n\nAnd this QSORT().\n\nThere are a few others, I won't list them all. The only tricky one I see\nis:\n\n> +\t\tfree(tree->buffer);\n> +\t\ttree->buffer = NULL;\n> +\t\ttree->object.parsed = 0;\n\nThis suggests FREE_AND_NULL(), but I think it actually the whole block\nshould become a call to free_tree_buffer().\n\n-Peff\n"},{"id":"353698","messageId":"20180727112950.GA18599@sigill.intra.peff.net","threadId":"48935","inReplyTo":"xmqqy3e0zjw0.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 1/5] packfile: make get_delta_base() non static","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-27T11:29:50Z","receivedAt":"2018-07-27T11:29:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 24, 2018 at 09:19:27AM -0700, Junio C Hamano wrote:\n\n> Christian Couder writes:\n> \n> > From: Jeff King \n> >\n> > As get_delta_base() will be used outside 'packfile.c' in\n> > a following commit, let's make it non static and let's\n> > declare it in 'packfile.h'.\n> \n> As a public function in *.h, don't we want a bit of comment there to\n> help those who want to use it from outside packfile.c?\n\nArguably it may want a better name, too.\n\n-Peff\n"},{"id":"353704","messageId":"20180727130229.GB18599@sigill.intra.peff.net","threadId":"48935","inReplyTo":"xmqqpnzczila.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-27T13:02:29Z","receivedAt":"2018-07-27T13:02:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 24, 2018 at 09:47:29AM -0700, Junio C Hamano wrote:\n\n> > +/*\n> > + * Allocate a new bitmap; if \"old\" is not NULL, the new bitmap will be a copy\n> > + * of \"old\". Otherwise, the new bitmap is empty.\n> > + */\n> > +static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old)\n> > +{\n> > +\tsize_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4);\n> > +\tstruct island_bitmap *b = xcalloc(1, size);\n> \n> Is one of the variants of flex array macros applicable here?\n\nHmm, maybe. The tricky thing about this bitmap (and this touches on your\n\"why another bitmap\" question below) is that we have a _ton_ of them\n(one per object). So we want to do what we can to keep memory usage\ndown. So there are two weird things:\n\n - these bitmaps do not know their own size. They are all exactly the\n same size (one bit per island), and we store the size only once in\n the whole program.\n\n - they are copy-on-write. This helps because there's a lot of\n locality to the maps within the object graph. But it also means\n sometimes we initialize empty, and sometimes from another array.\n\nSo I think it might work to do:\n\n if (old) {\n\t/* copy bits from existing bitmap */\n\tFLEX_ALLOC_MEM(b, bits, old->bits, st_mult(island_bitmap_size, 4));\n } else {\n\t/* start with all-zero bits courtesy of xcalloc */\n\tFLEX_ALLOC_MEM(b, bits, NULL, 0);\n }\n\nThat'd still waste an extra byte per struct (or 4, I guess, due to\npadding), since we unconditionally NUL-terminate the flex-struct (since\nthey were really designed around string storage).\n\n> > +static int island_bitmap_get(struct island_bitmap *self, uint32_t i)\n> > +{\n> > +\treturn (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0;\n> > +}\n> > +\n> \n> Not necessarily a complaint, but do we need another implementation\n> of bitmap here, or the compressed bitmap used for the pack bitmap is\n> unsuited for the purpose of this thing (e.g. perhaps it is overkill,\n> as we won't be shooting for saving disk footprint of a bitmap that\n> we are not going to save on disk anyway)?\n\nMostly it's about memory savings, as I discussed above. We _could_ use\newah bitmaps instead of naive ones here. Those are bad for random access\nto bits, but I think most of the operations are \"is this bitmap a subset\nof this other one\" which can be done by walking them linearly.\n\nI doubt the compression would be all that significant, though. They do\nbest when there's a lot of locality in the bitmap. Here our bits are the\nislands, grouped and ordered by some subset of the refname. I don't\nthink there's any reason to think that refs/heads/a and refs/heads/b\nwould be correlated. OTOH, if most objects are in most islands (e.g.,\nbecause the islands represent a bunch of forks of some \"base\" history),\nthen you might get a big run of 1's for those objects.\n\nI don't think we really experimented with it. To be honest, I don't\nrecall how much measuring we did for the refcounted bitmaps, either. So\nI'm not sure how much the copy-on-write saves (though my vague\nrecollection is that it was worth doing if you have a lot of islands).\n\n> > +\t/*\n> > +\t * We process only trees, as commits and tags have already been handled\n> > +\t * (and passed their marks on to root trees, as well. We must make sure\n> > +\t * to process them in descending tree-depth order so that marks\n> > +\t * propagate down the tree properly, even if a sub-tree is found in\n> > +\t * multiple parent trees.\n> > +\t */\n> > +\ttodo = xmalloc(to_pack->nr_objects * sizeof(*todo));\n> > +\tfor (i = 0; i < to_pack->nr_objects; i++) {\n> > +\t\tif (oe_type(&to_pack->objects[i]) == OBJ_TREE)\n> > +\t\t\ttodo[nr++] = &to_pack->objects[i];\n> > +\t}\n> > +\tqsort(todo, nr, sizeof(*todo), cmp_tree_depth);\n> \n> Hmph, at this stage nobody actually seems to set tree_depth; I am\n> wondering how a tree that is at the root in one commit but appears\n> as a subdirectory in another commit is handled by this code.\n\nThe tree depth is set when we actually walk the graph collecting\nobjects, and we use the max depth at which we've seen it. That said,\nthis happens in show_object(), which I think we'd avoid entering twice\nfor the same object (due to list-objects setting the SEEN flag).\n\nSo I suspect that yes, you could have a case where a tree has multiple\ndepths, and we'd visit them topologically out of order. And that could\nlead to objects reachable from that tree missing some of their islands.\nSomething like:\n\n - refs/remotes/123/master points to commit C which points to tree X,\n which points to blob B\n\n - refs/remotes/456/master points to commit D which points to tree Y,\n which points to tree X, which points to blob B\n\nWe mark C with island \"123\" and D with island \"456\", and ditto for their\nroot trees X and Y. Then we sort the trees by depth, with the intent\nthat Y would come before its child X. But due to the bogus depth, X may\ncome first. We propagate the mark for 123 down to children of X,\nincluding B. When we get to Y, we propagate the mark for 456 down to\ntree X. But we don't ever visit X again, because we assume we're going\nin topological order through the list.\n\nAnd we might decide not to allow a delta that we otherwise would\n(because B really is in both 123 and 456, but is only marked for one).\n\n> > +static regex_t *island_regexes;\n> > +static unsigned int island_regexes_alloc, island_regexes_nr;\n> > +static const char *core_island_name;\n> \n> Are these (and the bitmap & hashtable) something that \"everything in\n> the_repository\" folks would come in and nuke as global variables? I\n> haven't thought deeply about it, but these smell like that there\n> would be one set of such in-core variables per one in-core object\n> store plus refs (i.e. repository instance).\n\nI don't think so. They're really local to the single pack-objects operation, so\nthey're no worse than all the other file-local static globals.\n\n-Peff\n"},{"id":"353705","messageId":"20180727131333.GC18599@sigill.intra.peff.net","threadId":"48935","inReplyTo":"CAGZ79kZkagveB+jG9iLQ2ohaSfAzY5YtWC=BTdD1o9OQUrw90Q@mail.gmail.com","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-27T13:13:34Z","receivedAt":"2018-07-27T13:13:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 24, 2018 at 10:20:05AM -0700, Stefan Beller wrote:\n\n> So in my understanding we have a \"common base pack\" and specific\n> packs on top for each \"island\".\n\nSort of. This is another hacky part. The islands themselves are\ngenerally just about forbidding deltas, and not any particular kind of\nlayering.\n\nBut there's some magic layering only for the \"core\" island, which gets\nto go first (and makes a sort of pseudo-pack at the front of the one\npack). And then everything else is written willy nilly. This is a hack\nto try to make the \"blit the pack bytes out\" code path for cloning fast.\nAnd that has to pick _one_ winner, so ideally you'd point it at the\nthing that gets cloned the most, and everybody else gets to be a loser.\n\nAgain, this was designed for the current pack-reuse code we have\nupstream, which we (GitHub) found to be pretty crappy (which I feel\njustified in saying as one of the authors). I need to clean up and share\nthe alternative strategy we ended up with.\n\n> Do you envision to have \"groups of islands\" (an atoll) for say all\n> open source clones of linux.git, such that you can layer the packs?\n> You would not just have the base pack + island pack, but have one\n> pack that is common to most islands?\n\nSo no, we don't really layer in any sane way. If pack-objects were fed\nthe topological relationships between the forks, in theory we could\ncreate a layered packfile that respects that.\n\nBut even that is not quite enough. At the time of forking, you might\nimagine that torvalds/linux has the base pack, and then somebody forks\nfrom them and contains all of those objects plus more, and somebody\nforks from them, and so on. But that's just a snapshot. Later\ntorvalds/linux will get a bunch of new objects pushed to it. And some of\nits forks will merge those objects, too. But some of them will just rot,\nabandoned, as nobody ever touches them again.\n\nSo I don't think there's much to be gained by paying attention to the\nexternal forking relationships. We have to discover afresh the\nrelationships between objects, and which refs (and thus which islands)\npoint to them.\n\nOne thing I don't think we ever tried was doubling down on the\nislandCore concept and making the \"root\" fork as tightly packed as it\ncould be (with the assumption that _most_ people grab that). And then\njust respect the islands for all the other objects (remember this is an\noptimization, so the worst case is somebody asks for an object during a\nfetch and we have to throw away its on-disk delta).\n\nThat would solve the problem that fetching torvalds/linux from GitHub\nyields a bigger pack than fetching it from kernel.org. But again, it's\nmaking that root fork weirdly magical. People who fetch solely from\nother forks won't get any benefit (and may even see worse packs).\n\n-Peff\n"},{"id":"353731","messageId":"CAGZ79kYK3QkaSEinuq_Js5thVgY2-MyrN60W-Dws1p4eK73hHw@mail.gmail.com","threadId":"48935","inReplyTo":"20180727131333.GC18599@sigill.intra.peff.net","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-07-27T17:22:09Z","receivedAt":"2018-07-27T17:22:23Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Jul 27, 2018 at 6:13 AM Jeff King wrote:\n>\n> On Tue, Jul 24, 2018 at 10:20:05AM -0700, Stefan Beller wrote:\n>\n> > So in my understanding we have a \"common base pack\" and specific\n> > packs on top for each \"island\".\n>\n> Sort of. This is another hacky part. The islands themselves are\n> generally just about forbidding deltas, and not any particular kind of\n> layering.\n>\n> But there's some magic layering only for the \"core\" island, which gets\n> to go first (and makes a sort of pseudo-pack at the front of the one\n> pack). And then everything else is written willy nilly. This is a hack\n> to try to make the \"blit the pack bytes out\" code path for cloning fast.\n\nyup, I do understand its purpose; we had the same discussions here\nfor the JGit based hosting.\n\nSo you are saying island hopping is disallowed, but the core island\nhas an airport using the spokes system to reach all other islands?\n(I described the core island as sea bed before). Sounds reasonable.\n\n> So no, we don't really layer in any sane way. If pack-objects were fed\n> the topological relationships between the forks, in theory we could\n> create a layered packfile that respects that.\n>\n> But even that is not quite enough. At the time of forking, you might\n> imagine that torvalds/linux has the base pack, and then somebody forks\n> from them and contains all of those objects plus more, and somebody\n> forks from them, and so on. But that's just a snapshot. Later\n> torvalds/linux will get a bunch of new objects pushed to it. And some of\n> its forks will merge those objects, too. But some of them will just rot,\n> abandoned, as nobody ever touches them again.\n>\n> So I don't think there's much to be gained by paying attention to the\n> external forking relationships. We have to discover afresh the\n> relationships between objects, and which refs (and thus which islands)\n> point to them.\n>\n> One thing I don't think we ever tried was doubling down on the\n> islandCore concept and making the \"root\" fork as tightly packed as it\n> could be (with the assumption that _most_ people grab that). And then\n> just respect the islands for all the other objects (remember this is an\n> optimization, so the worst case is somebody asks for an object during a\n> fetch and we have to throw away its on-disk delta).\n>\n> That would solve the problem that fetching torvalds/linux from GitHub\n> yields a bigger pack than fetching it from kernel.org. But again, it's\n> making that root fork weirdly magical. People who fetch solely from\n> other forks won't get any benefit (and may even see worse packs).\n\nThanks for the explanation.\nI think this discussion just hints at me being dense reading the\ndocumentation. After all I like the concept.\n\nThanks,\nStefan\n"},{"id":"353791","messageId":"20180728090044.GA16454@sigill.intra.peff.net","threadId":"48935","inReplyTo":"CAGZ79kYK3QkaSEinuq_Js5thVgY2-MyrN60W-Dws1p4eK73hHw@mail.gmail.com","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-07-28T09:00:45Z","receivedAt":"2018-07-28T09:00:48Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 27, 2018 at 10:22:09AM -0700, Stefan Beller wrote:\n\n> > That would solve the problem that fetching torvalds/linux from GitHub\n> > yields a bigger pack than fetching it from kernel.org. But again, it's\n> > making that root fork weirdly magical. People who fetch solely from\n> > other forks won't get any benefit (and may even see worse packs).\n> \n> Thanks for the explanation.\n> I think this discussion just hints at me being dense reading the\n> documentation. After all I like the concept.\n\nI actually think it hints that the documentation in the commits\nthemselves is not adequate. :)\n\n-Peff\n"},{"id":"353797","messageId":"CAP8UFD3McRRGNheftV9qmJMQ1i860tNPefFT=+X_TZtpDGLzKg@mail.gmail.com","threadId":"48935","inReplyTo":"20180728090044.GA16454@sigill.intra.peff.net","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-07-28T12:12:08Z","receivedAt":"2018-07-28T12:12:11Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sat, Jul 28, 2018 at 11:00 AM, Jeff King wrote:\n>\n> On Fri, Jul 27, 2018 at 10:22:09AM -0700, Stefan Beller wrote:\n>\n> > > That would solve the problem that fetching torvalds/linux from GitHub\n> > > yields a bigger pack than fetching it from kernel.org. But again, it's\n> > > making that root fork weirdly magical. People who fetch solely from\n> > > other forks won't get any benefit (and may even see worse packs).\n> >\n> > Thanks for the explanation.\n> > I think this discussion just hints at me being dense reading the\n> > documentation. After all I like the concept.\n>\n> I actually think it hints that the documentation in the commits\n> themselves is not adequate. :)\n\nOk, I will try to improve it using information from the discussion threads.\n\nThanks,\nChristian.\n"},{"id":"354571","messageId":"CAP8UFD38--s_yCsQYu5Ou++7g15L11Bw-YcUByRxxE5yyrDjzQ@mail.gmail.com","threadId":"48935","inReplyTo":"CACsJy8CmJt1Wj=e4TNUUxY-Czn+h0BTVAWLY0ujJhgUKC+Y6yw@mail.gmail.com","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-05T17:28:06Z","receivedAt":"2018-08-05T17:28:09Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sun, Jul 22, 2018 at 10:55 AM, Duy Nguyen wrote:\n> On Sun, Jul 22, 2018 at 7:52 AM Christian Couder\n> wrote:\n>>\n>> - /*\n>> - * And then all remaining commits and tags.\n>> - */\n>> - for (i = last_untagged; i < to_pack.nr_objects; i++) {\n>> - if (oe_type(&objects[i]) != OBJ_COMMIT &&\n>> - oe_type(&objects[i]) != OBJ_TAG)\n>> - continue;\n>> - add_to_write_order(wo, &wo_end, &objects[i]);\n>> - }\n>> + /*\n>> + * Then fill all the tagged tips.\n>> + */\n>\n> If we move the code in this loop to a separate function, in a separate\n> patch, first, would it produce a better diff? I think all the\n> indentation change here makes it a bit hard to read.\n\nSorry I just realized that I forgot to try to do that. It will be on\nmy todo list for the next iteration.\n\nThanks,\nChristian.\n"},{"id":"354572","messageId":"CAP8UFD2Ri6N33UhZSHOvxtxiCBC13-1rpa_ZByY9dsyPjmaC8A@mail.gmail.com","threadId":"48935","inReplyTo":"xmqqfu08zhh7.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-05T17:40:19Z","receivedAt":"2018-08-05T17:40:23Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Jul 24, 2018 at 7:11 PM, Junio C Hamano wrote:\n>\n> Another thing I noticed from 2/5 is that you can have up to 7 such\n> capture groups. I do not have any opinion if 7 is too few or too\n> many, but we would want the number to be documented, and end-user\n> input diagnosed when it requires more captures than we support (if\n> we are not already checking, that is).\n\nThis is the new documentation:\n\n-> Refs are grouped into islands based on their \"names\", and two regexes\n-> that produce the same name are considered to be in the same\n-> island. The names are computed from the regexes by concatenating any\n-> capture groups from the regex, with a '-' dash in between. (And if\n-> there are no capture groups, then the name is the empty string, as in\n-> the above example.) This allows you to create arbitrary numbers of\n-> islands. Only up to 7 such capture groups are supported though.\n\nI added the last sentence above, but I wonder if it is 7 or 8. The\ncode is the following:\n\n-> static int find_island_for_ref(const char *refname, const struct\nobject_id *oid,\n-> int flags, void *data)\n-> {\n-> int i, m;\n-> regmatch_t matches[8];\n-> struct strbuf island_name = STRBUF_INIT;\n->\n-> /* walk backwards to get last-one-wins ordering */\n-> for (i = island_regexes_nr - 1; i >= 0; i--) {\n-> if (!regexec(&island_regexes[i], refname,\n-> ARRAY_SIZE(matches), matches, 0))\n-> break;\n-> }\n\nI also wonder if the above is enough to diagnose end-user input when\nit requires more captures than we support. A quick look at the man\npage of the regex functions wasn't enough to enlighten me. Any input\non these issues is very welcome!\n"},{"id":"354575","messageId":"CAP8UFD2frOjmZoOfWW-93xewA6LS5zTEisNr4QDz2FNQE2DY_A@mail.gmail.com","threadId":"48935","inReplyTo":"CACsJy8AzksB=rfaX_dfboMXHjqj6gj+erdF6eRFAKmWA1-3PUg@mail.gmail.com","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-05T18:53:19Z","receivedAt":"2018-08-05T18:53:22Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sun, Jul 22, 2018 at 10:50 AM, Duy Nguyen wrote:\n> On Sun, Jul 22, 2018 at 7:51 AM Christian Couder\n> wrote:\n\n>> diff --git a/pack-objects.h b/pack-objects.h\n>> index edf74dabdd..8eecd67991 100644\n>> --- a/pack-objects.h\n>> +++ b/pack-objects.h\n>> @@ -100,6 +100,10 @@ struct object_entry {\n>> unsigned type_:TYPE_BITS;\n>> unsigned no_try_delta:1;\n>> unsigned in_pack_type:TYPE_BITS; /* could be delta */\n>> +\n>> + unsigned int tree_depth; /* should be repositioned for packing? */\n>> + unsigned char layer;\n>> +\n>\n> This looks very much like an optional feature. To avoid increasing\n> pack-objects memory usage for common case, please move this to struct\n> packing_data.\n\nAs you can see the patch 6/6 (in the v2 of this patch series that I\njust sent) moves `unsigned int tree_depth` from 'struct object_entry'\nto 'struct packing_data'. I am not sure that I did it right and that\nit is worth it though as it is a bit more complex.\n\nAbout `unsigned char layer` I am even less sure that it's worth it for\nthe following reasons:\n\n- 'struct object_entry' contains bit fields as its last members and\nthen the following comment:\n\n /*\n * pahole results on 64-bit linux (gcc and clang)\n *\n * size: 80, bit_padding: 20 bits, holes: 8 bits\n *\n * and on 32-bit (gcc)\n *\n * size: 76, bit_padding: 20 bits, holes: 8 bits\n */\n\nI am not sure if this comment is still up to date, but if it true\nmaybe there is enough space in the padding to add 'layer' as a 8 bit\nbit field somewhere without increasing the size of 'struct\nobject_entry'.\n\n- 'layer' is used in add_to_write_order() which is called from many\nplaces in add_descendants_to_write_order() and compute_write_order()\nfor example like this:\n\n for (s = DELTA_SIBLING(e); s; s = DELTA_SIBLING(s)) {\n add_to_write_order(wo, endp, s);\n }\n\nSo it seems to me that moving 'layer' to 'struct packing_data' would\nrequire changing the DELTA_SIBLING macros or adding a hack to easily\nfind the index in an array corresponding to a 'struct object_entry'.\n\n- I don't see why it is different from other fields in 'struct\nobject_entry' that are also used in compute_write_order(), for\nexample:\n\n uint32_t delta_idx; /* delta base object */\n uint32_t delta_child_idx; /* deltified objects who bases me */\n uint32_t delta_sibling_idx; /* other deltified objects who ... */\n\nWould we also want to move these fields to 'struct packing_data'? Why\nor why not? If we want to move them, then it might be a good idea to\ndo all the moving at the same time to make sure we get something\ncoherent.\n\nThanks,\nChristian.\n"},{"id":"354587","messageId":"CAP8UFD3uruf94d7eV9Fy25h19y_KV8uZeaZN71F_xFM2XrspWQ@mail.gmail.com","threadId":"48935","inReplyTo":"CAP8UFD2Ri6N33UhZSHOvxtxiCBC13-1rpa_ZByY9dsyPjmaC8A@mail.gmail.com","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-06T08:44:14Z","receivedAt":"2018-08-06T08:44:18Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Sun, Aug 5, 2018 at 7:40 PM, Christian Couder\n wrote:\n> On Tue, Jul 24, 2018 at 7:11 PM, Junio C Hamano wrote:\n\n> This is the new documentation:\n>\n> -> Refs are grouped into islands based on their \"names\", and two regexes\n> -> that produce the same name are considered to be in the same\n> -> island. The names are computed from the regexes by concatenating any\n> -> capture groups from the regex, with a '-' dash in between. (And if\n> -> there are no capture groups, then the name is the empty string, as in\n> -> the above example.) This allows you to create arbitrary numbers of\n> -> islands. Only up to 7 such capture groups are supported though.\n>\n> I added the last sentence above, but I wonder if it is 7 or 8.\n\nActually after reading the man page again, it looks like the first\nelement in the array we pass is used for \"the entire regular\nexpression's match addresses\", so we only get 7 capture groups (not\n8).\n\n> The code is the following:\n>\n> -> static int find_island_for_ref(const char *refname, const struct\n> object_id *oid,\n> -> int flags, void *data)\n> -> {\n> -> int i, m;\n> -> regmatch_t matches[8];\n> -> struct strbuf island_name = STRBUF_INIT;\n> ->\n> -> /* walk backwards to get last-one-wins ordering */\n> -> for (i = island_regexes_nr - 1; i >= 0; i--) {\n> -> if (!regexec(&island_regexes[i], refname,\n> -> ARRAY_SIZE(matches), matches, 0))\n> -> break;\n> -> }\n>\n> I also wonder if the above is enough to diagnose end-user input when\n> it requires more captures than we support. A quick look at the man\n> page of the regex functions wasn't enough to enlighten me. Any input\n> on these issues is very welcome!\n\nTaking a look at how we use regexec() in our code base, it looks like\nit might be better to use regexec_buf() defined in\n\"git-compat-util.h\".\n\nI am not completely sure about that because apply.c has:\n\n status = regexec(stamp, timestamp, ARRAY_SIZE(m), m, 0);\n if (status) {\n if (status != REG_NOMATCH)\n warning(_(\"regexec returned %d for input: %s\"),\n status, timestamp);\n return 0;\n }\n\nThough the above uses a regex that is defined in apply.c. The regex\ndoesn't come from the config file.\n\nActually except the above there is a mix of regexec() and\nregexec_buf() in our code base, which are used with only 0, 1 or 2\ncapture groups, so it is not very clear what should be used.\n\nAnd anyway I still don't see how we could diagnose when the end user\ninput requires more captures than we support.\n"},{"id":"354603","messageId":"20180806135855.GC31282@sigill.intra.peff.net","threadId":"48935","inReplyTo":"CAP8UFD3uruf94d7eV9Fy25h19y_KV8uZeaZN71F_xFM2XrspWQ@mail.gmail.com","subject":"Re: [RFC PATCH 3/5] pack-objects: add delta-islands support","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-06T13:58:55Z","receivedAt":"2018-08-06T13:58:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Aug 06, 2018 at 10:44:14AM +0200, Christian Couder wrote:\n\n> Taking a look at how we use regexec() in our code base, it looks like\n> it might be better to use regexec_buf() defined in\n> \"git-compat-util.h\".\n> \n> I am not completely sure about that because apply.c has:\n> \n> status = regexec(stamp, timestamp, ARRAY_SIZE(m), m, 0);\n> if (status) {\n> if (status != REG_NOMATCH)\n> warning(_(\"regexec returned %d for input: %s\"),\n> status, timestamp);\n> return 0;\n> }\n> \n> Though the above uses a regex that is defined in apply.c. The regex\n> doesn't come from the config file.\n> \n> Actually except the above there is a mix of regexec() and\n> regexec_buf() in our code base, which are used with only 0, 1 or 2\n> capture groups, so it is not very clear what should be used.\n\nI don't think we need regexec_buf(). The advantage it has is that it can\noperate on strings that aren't NUL-terminated, but that isn't the case\nhere.\n\n> And anyway I still don't see how we could diagnose when the end user\n> input requires more captures than we support.\n\nWe can use the final element as a sentinel, and complain if it gets\nfilled in:\n\ndiff --git a/delta-islands.c b/delta-islands.c\nindex dcc6590cc1..18426ffb18 100644\n--- a/delta-islands.c\n+++ b/delta-islands.c\n@@ -375,6 +375,10 @@ static int find_island_for_ref(const char *refname, const struct object_id *oid,\n \tif (i < 0)\n \t\treturn 0;\n \n+\tif (matches[ARRAY_SIZE(matches)-1].rm_so != -1)\n+\t\tdie(\"island regex had too many matches (max=%d)\",\n+\t\t (int)ARRAY_SIZE(matches) - 2);\n+\n \tfor (m = 1; m < ARRAY_SIZE(matches); m++) {\n \t\tregmatch_t *match = &matches[m];\n \n\nThe big downside is that it only kicks in when you actually successfully\nmake a match. So you could have:\n\n [pack]\n island = refs/(one)/(two)/(three)/(four)/(five)/(six)/(seven)\n\nin your config for years, and then one day it blows up when somebody\nactually has a ref that matches it.\n\nI think it would be fine to just say \"we only respect the first N\ncapture groups\". And maybe even issue a warning (based on the detection\nabove). I'd also be fine with bumping the \"matches\" array to something\nmore ridiculous, like 32. The current value of 8 was supposed to be\nridiculous already (we've never used more than 2).\n\n-Peff\n"},{"id":"354605","messageId":"20180806141733.GD31282@sigill.intra.peff.net","threadId":"48935","inReplyTo":"CAP8UFD2frOjmZoOfWW-93xewA6LS5zTEisNr4QDz2FNQE2DY_A@mail.gmail.com","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-06T14:17:33Z","receivedAt":"2018-08-06T14:17:37Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Aug 05, 2018 at 08:53:19PM +0200, Christian Couder wrote:\n\n> - 'layer' is used in add_to_write_order() which is called from many\n> places in add_descendants_to_write_order() and compute_write_order()\n> for example like this:\n> \n> for (s = DELTA_SIBLING(e); s; s = DELTA_SIBLING(s)) {\n> add_to_write_order(wo, endp, s);\n> }\n> \n> So it seems to me that moving 'layer' to 'struct packing_data' would\n> require changing the DELTA_SIBLING macros or adding a hack to easily\n> find the index in an array corresponding to a 'struct object_entry'.\n\nRight, that hack is how the various the existing memory-shrinking macros\nwork. Every \"struct object_entry *\" that we deal with _must_ be in the\nlist in \"packing_data\", so that we can compute an index as\n\"entry - to_pack.objects\".\n\nSo I think Duy is just suggesting:\n\n void oe_set_layer(struct packing_data *pack,\n struct object_entry *entry,\n\t\t int layer)\n {\n if (!pack->layers)\n\t ALLOC_ARRAY(pack->layers, pack->nr_objects);\n\t pack->layers[entry - pack->objects] = layer;\n }\n\n int oe_get_layer(struct packing_data *pack,\n struct object_entry *entry)\n {\n if (!pack->layers)\n\t return 0;\n return pack->layers[entry - pack->nr_objects];\n }\n\nThat said, I wonder if need to cache the layer at all. We compute the\nlayers all at once in the new compute_pack_layers(). But it is just a\nlinear walk over the objects, asking for each \"is this in the core\nisland?\".\n\nCould we just ask \"is this in the core island?\" when we consider each\nobject? That's a hash lookup each time we ask instead of looking at our\nint, but I'd think we would only ask in linear proportion to the number\nof objects. So there's no algorithmic speedup, though maybe a\nconstant-time one (for two layers, I'd expect we'd probably ask about\neach object twice).\n\n> - I don't see why it is different from other fields in 'struct\n> object_entry' that are also used in compute_write_order(), for\n> example:\n> \n> uint32_t delta_idx; /* delta base object */\n> uint32_t delta_child_idx; /* deltified objects who bases me */\n> uint32_t delta_sibling_idx; /* other deltified objects who ... */\n> \n> Would we also want to move these fields to 'struct packing_data'? Why\n> or why not? If we want to move them, then it might be a good idea to\n> do all the moving at the same time to make sure we get something\n> coherent.\n\nWe actually use those multiple times. They're reset and used in\ncompute_write_order(), but I think we use them earlier as part of the\ndelta search (at the very least we use delta_idx; maybe no the\nchild/sibling stuff).\n\n-Peff\n"},{"id":"354632","messageId":"CACsJy8Aa2xo+jVOPza_wt-EX8P4_M8XJD3jdLs=cr11M0ckUuA@mail.gmail.com","threadId":"48935","inReplyTo":"CAP8UFD2frOjmZoOfWW-93xewA6LS5zTEisNr4QDz2FNQE2DY_A@mail.gmail.com","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-08-06T15:53:57Z","receivedAt":"2018-08-06T15:54:26Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sun, Aug 5, 2018 at 8:53 PM Christian Couder\n wrote:\n>\n> On Sun, Jul 22, 2018 at 10:50 AM, Duy Nguyen wrote:\n> > On Sun, Jul 22, 2018 at 7:51 AM Christian Couder\n> > wrote:\n>\n> >> diff --git a/pack-objects.h b/pack-objects.h\n> >> index edf74dabdd..8eecd67991 100644\n> >> --- a/pack-objects.h\n> >> +++ b/pack-objects.h\n> >> @@ -100,6 +100,10 @@ struct object_entry {\n> >> unsigned type_:TYPE_BITS;\n> >> unsigned no_try_delta:1;\n> >> unsigned in_pack_type:TYPE_BITS; /* could be delta */\n> >> +\n> >> + unsigned int tree_depth; /* should be repositioned for packing? */\n> >> + unsigned char layer;\n> >> +\n> >\n> > This looks very much like an optional feature. To avoid increasing\n> > pack-objects memory usage for common case, please move this to struct\n> > packing_data.\n>\n> As you can see the patch 6/6 (in the v2 of this patch series that I\n> just sent) moves `unsigned int tree_depth` from 'struct object_entry'\n> to 'struct packing_data'. I am not sure that I did it right and that\n> it is worth it though as it is a bit more complex.\n\nIt is a bit more complex than I expected. But I think if you go with\nJeff's suggestion (i.e. think of the new tree_depth array an extension\nof objects array) it's a bit simpler: you access both arrays using the\nsame index, both arrays should have the same size and be realloc'd at\nthe same time in packlist_alloc().\n\nIs it worth it? The \"pahole\" comment in this file is up to date. We\nuse 80 bytes per object. This series makes the struct 88 bytes (I've\njust rerun pahole). On linux repo with 12M objects, \"git pack-objects\n--all\" needs extra 96MB memory even if this feature is not used. So\nyes I still think it's worth moving these fields out of struct\nobject_entry.\n-- \nDuy\n"},{"id":"354667","messageId":"CAP8UFD35j1KkO=hB58Qcs=PZTFW2=djGi07z5uyayDENXzanwA@mail.gmail.com","threadId":"48935","inReplyTo":"CACsJy8Aa2xo+jVOPza_wt-EX8P4_M8XJD3jdLs=cr11M0ckUuA@mail.gmail.com","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2018-08-06T18:54:53Z","receivedAt":"2018-08-06T18:54:57Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Mon, Aug 6, 2018 at 5:53 PM, Duy Nguyen wrote:\n> On Sun, Aug 5, 2018 at 8:53 PM Christian Couder\n> wrote:\n>>\n>> As you can see the patch 6/6 (in the v2 of this patch series that I\n>> just sent) moves `unsigned int tree_depth` from 'struct object_entry'\n>> to 'struct packing_data'. I am not sure that I did it right and that\n>> it is worth it though as it is a bit more complex.\n>\n> It is a bit more complex than I expected. But I think if you go with\n> Jeff's suggestion (i.e. think of the new tree_depth array an extension\n> of objects array) it's a bit simpler: you access both arrays using the\n> same index, both arrays should have the same size and be realloc'd at\n> the same time in packlist_alloc().\n\nOk, I will take a look at doing that to simplify things. Thanks to\nPeff and you for that suggestion!\n\n> Is it worth it? The \"pahole\" comment in this file is up to date. We\n> use 80 bytes per object. This series makes the struct 88 bytes (I've\n> just rerun pahole).\n\nDid you run it on V1 or on V2? I guess on V2, but then what do you\nthink about converting the 'layer' field into a bit field, which might\nbe simpler and save space?\n\n> On linux repo with 12M objects, \"git pack-objects\n> --all\" needs extra 96MB memory even if this feature is not used. So\n> yes I still think it's worth moving these fields out of struct\n> object_entry.\n\nAnd what about the fields already in struct object_entry? While I am\nat it, I think I could move some of them too if it is really so worth\nit.\n"},{"id":"354673","messageId":"CACsJy8D_V5d4y1cYhBveq8yxrwUPeuiqmgGyQJYTC2V0Zye-Tw@mail.gmail.com","threadId":"48935","inReplyTo":"CAP8UFD35j1KkO=hB58Qcs=PZTFW2=djGi07z5uyayDENXzanwA@mail.gmail.com","subject":"Re: [RFC PATCH 2/5] Add delta-islands.{c,h}","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2018-08-06T19:21:07Z","receivedAt":"2018-08-06T19:21:36Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Mon, Aug 6, 2018 at 8:54 PM Christian Couder\n wrote:\n> > Is it worth it? The \"pahole\" comment in this file is up to date. We\n> > use 80 bytes per object. This series makes the struct 88 bytes (I've\n> > just rerun pahole).\n>\n> Did you run it on V1 or on V2? I guess on V2, but then what do you\n> think about converting the 'layer' field into a bit field, which might\n> be simpler and save space?\n\nV2. I kinda ignored the layer field because Jeff was suggesting that\nit may not be needed. It may be better to just move it out though\nbecause it's not that complicated and even if we have enough bits\nleft, they may be spread out that it's hard to reorder so that they're\ngrouped together and use can use them.\n\n> > On linux repo with 12M objects, \"git pack-objects\n> > --all\" needs extra 96MB memory even if this feature is not used. So\n> > yes I still think it's worth moving these fields out of struct\n> > object_entry.\n>\n> And what about the fields already in struct object_entry? While I am\n> at it, I think I could move some of them too if it is really so worth\n\nWay ahead of you. In v2.17.0 this struct is 136 bytes so going down to\n80 bytes now is a big memory saving. I think I squeezed everything\npossible and was a bit too aggressive that I created a new performance\nregression in v2.18.0 ;-)\n-- \nDuy\n"}]}