{"thread":{"id":"52480","subject":"[PATCH v4 00/12] Rewrite packfile reuse code","startedAt":"2019-12-18T11:26:09Z","lastAt":"2019-12-18T11:26:26Z","messageCount":13,"participants":["Christian Couder"],"isPatch":true,"patchVersion":4,"patchTotal":12},"messages":[{"id":"388423","messageId":"20191218112547.4974-1-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":null,"subject":"[PATCH v4 00/12] Rewrite packfile reuse code","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:35Z","receivedAt":"2019-12-18T11:26:09Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This patch series is rewriting the code that tries to reuse existing\npackfiles.\n\nThe code in this patch series was written by GitHub, and Peff nicely\nprovided it in the following discussion:\n\nhttps://public-inbox.org/git/3E56B0FD-EBE8-4057-A93A-16EBB09FBCE0@jramsay.com.au/\n\nThe first versions of this patch series were also discussed:\n\nv3: https://public-inbox.org/git/20191115141541.11149-1-chriscool@tuxfamily.org/\nV2: https://public-inbox.org/git/20191019103531.23274-1-chriscool@tuxfamily.org/\nV1: https://public-inbox.org/git/20190913130226.7449-1-chriscool@tuxfamily.org/\n\nThanks to the reviewers!\n\nAccording to Peff this new code is a lot smarter than what it\nreplaces. It allows \"holes\" in the chunks of packfile to be reused,\nand skips over them. It rewrites OFS_DELTA offsets as it goes to\naccount for the holes. So it's basically a linear walk over the\npackfile, but with the important distinction that we don't add those\nobjects to the object_entry array, which makes them very lightweight\n(especially in memory use, but they also aren't considered bases for\nfinding new deltas, etc). It seems like a good compromise between the\ncost to serve a clone and the quality of the resulting packfile.\n\nThis series has been rebased onto current master ad05a3d8e5 (The fifth\nbatch, 2019-12-10).\n\nOther changes since the previous patch series have all been suggested\nby Peff. Thanks to him! They are the following:\n\n - Add note in commit message of patch 3/12.\n\n - Move previous patch 4/9 to patch 12/12 at the end of the series to\n avoid test failures.\n\n - Add new patches 5/12 and 6/12.\n\n - Improve commit message and documentation of pack.allowPackReuse in\n patch 8/12.\n\n - Improve commit message of patch 10/12.\n\n - Extract patch 11/12 from patch 10/12.\n\nJeff King (12):\n builtin/pack-objects: report reused packfile objects\n packfile: expose get_delta_base()\n ewah/bitmap: introduce bitmap_word_alloc()\n pack-bitmap: introduce bitmap_walk_contains()\n pack-bitmap: uninteresting oid can be outside bitmapped packfile\n pack-bitmap: simplify bitmap_has_oid_in_uninteresting()\n csum-file: introduce hashfile_total()\n pack-objects: introduce pack.allowPackReuse\n builtin/pack-objects: introduce obj_is_packed()\n pack-objects: improve partial packfile reuse\n pack-objects: add checks for duplicate objects\n pack-bitmap: don't rely on bitmap_git->reuse_objects\n\n Documentation/config/pack.txt | 7 +\n builtin/pack-objects.c | 243 +++++++++++++++++++++++++++-------\n csum-file.h | 9 ++\n ewah/bitmap.c | 13 +-\n ewah/ewok.h | 1 +\n pack-bitmap.c | 192 ++++++++++++++++++---------\n pack-bitmap.h | 6 +-\n packfile.c | 10 +-\n packfile.h | 3 +\n 9 files changed, 362 insertions(+), 122 deletions(-)\n\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388424","messageId":"20191218112547.4974-2-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 01/12] builtin/pack-objects: report reused packfile objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:36Z","receivedAt":"2019-12-18T11:26:11Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nTo see when packfile reuse kicks in or not, it is useful to\nshow reused packfile objects statistics in the output of\nupload-pack.\n\nHelped-by: James Ramsay \nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 393c20a2d7..369f46fbc5 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3509,7 +3509,9 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)\n \tif (progress)\n \t\tfprintf_ln(stderr,\n \t\t\t _(\"Total %\"PRIu32\" (delta %\"PRIu32\"),\"\n-\t\t\t \" reused %\"PRIu32\" (delta %\"PRIu32\")\"),\n-\t\t\t written, written_delta, reused, reused_delta);\n+\t\t\t \" reused %\"PRIu32\" (delta %\"PRIu32\"),\"\n+\t\t\t \" pack-reused %\"PRIu32),\n+\t\t\t written, written_delta, reused, reused_delta,\n+\t\t\t reuse_packfile_objects);\n \treturn 0;\n }\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388425","messageId":"20191218112547.4974-4-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 03/12] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:38Z","receivedAt":"2019-12-18T11:26:13Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nIn a following commit we will need to allocate a variable\nnumber of bitmap words, instead of always 32, so let's add\nbitmap_word_alloc() for this purpose.\n\nNote that we have to adjust the block growth in bitmap_set(),\nsince a caller could now use an initial size of \"0\" (we don't\nplan to do that, but it doesn't hurt to be defensive).\n\nHelped-by: Jonathan Tan \nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n ewah/bitmap.c | 13 +++++++++----\n ewah/ewok.h | 1 +\n 2 files changed, 10 insertions(+), 4 deletions(-)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 52f1178db4..b5fed9621f 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -22,21 +22,26 @@\n #define EWAH_MASK(x) ((eword_t)1 << (x % BITS_IN_EWORD))\n #define EWAH_BLOCK(x) (x / BITS_IN_EWORD)\n \n-struct bitmap *bitmap_new(void)\n+struct bitmap *bitmap_word_alloc(size_t word_alloc)\n {\n \tstruct bitmap *bitmap = xmalloc(sizeof(struct bitmap));\n-\tbitmap->words = xcalloc(32, sizeof(eword_t));\n-\tbitmap->word_alloc = 32;\n+\tbitmap->words = xcalloc(word_alloc, sizeof(eword_t));\n+\tbitmap->word_alloc = word_alloc;\n \treturn bitmap;\n }\n \n+struct bitmap *bitmap_new(void)\n+{\n+\treturn bitmap_word_alloc(32);\n+}\n+\n void bitmap_set(struct bitmap *self, size_t pos)\n {\n \tsize_t block = EWAH_BLOCK(pos);\n \n \tif (block >= self->word_alloc) {\n \t\tsize_t old_size = self->word_alloc;\n-\t\tself->word_alloc = block * 2;\n+\t\tself->word_alloc = block ? block * 2 : 1;\n \t\tREALLOC_ARRAY(self->words, self->word_alloc);\n \t\tmemset(self->words + old_size, 0x0,\n \t\t\t(self->word_alloc - old_size) * sizeof(eword_t));\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 84b2a29faa..1b98b57c8b 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -172,6 +172,7 @@ struct bitmap {\n };\n \n struct bitmap *bitmap_new(void);\n+struct bitmap *bitmap_word_alloc(size_t word_alloc);\n void bitmap_set(struct bitmap *self, size_t pos);\n int bitmap_get(struct bitmap *self, size_t pos);\n void bitmap_reset(struct bitmap *self);\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388426","messageId":"20191218112547.4974-3-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 02/12] packfile: expose get_delta_base()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:37Z","receivedAt":"2019-12-18T11:26:14Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nIn a following commit get_delta_base() will be used outside\npackfile.c, so let's make it non static and declare it in\npackfile.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 355066de17..81e66847bf 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1173,11 +1173,11 @@ const struct packed_git *has_packed_and_bad(struct repository *r,\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 fc7904ec81..ec536a4ae5 100644\n--- a/packfile.h\n+++ b/packfile.h\n@@ -151,6 +151,9 @@ void *unpack_entry(struct repository *r, struct packed_git *, off_t, enum object\n unsigned long unpack_object_header_buffer(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);\n unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);\n int unpack_object_header(struct packed_git *, struct pack_window **, off_t *, unsigned long *);\n+off_t get_delta_base(struct packed_git *p, struct pack_window **w_curs,\n+\t\t off_t *curpos, enum object_type type,\n+\t\t off_t delta_obj_offset);\n \n void release_pack_memory(size_t);\n \n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388427","messageId":"20191218112547.4974-5-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 04/12] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:39Z","receivedAt":"2019-12-18T11:26:15Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nWe will use this helper function in a following commit to\ntell us if an object is packed.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n pack-bitmap.c | 12 ++++++++++++\n pack-bitmap.h | 3 +++\n 2 files changed, 15 insertions(+)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex e07c798879..fb4f6297f2 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -830,6 +830,18 @@ int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n \treturn 0;\n }\n \n+int bitmap_walk_contains(struct bitmap_index *bitmap_git,\n+\t\t\t struct bitmap *bitmap, const struct object_id *oid)\n+{\n+\tint idx;\n+\n+\tif (!bitmap)\n+\t\treturn 0;\n+\n+\tidx = bitmap_position(bitmap_git, oid);\n+\treturn idx >= 0 && bitmap_get(bitmap, idx);\n+}\n+\n void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,\n \t\t\t\t show_reachable_fn show_reachable)\n {\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 466c5afa09..6ab6033dbe 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -3,6 +3,7 @@\n \n #include \"ewah/ewok.h\"\n #include \"khash.h\"\n+#include \"pack.h\"\n #include \"pack-objects.h\"\n \n struct commit;\n@@ -53,6 +54,8 @@ int reuse_partial_packfile_from_bitmap(struct bitmap_index *,\n int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping,\n \t\t\t kh_oid_map_t *reused_bitmaps, int show_progress);\n void free_bitmap_index(struct bitmap_index *);\n+int bitmap_walk_contains(struct bitmap_index *,\n+\t\t\t struct bitmap *bitmap, const struct object_id *oid);\n \n /*\n * After a traversal has been performed by prepare_bitmap_walk(), this can be\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388428","messageId":"20191218112547.4974-6-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 05/12] pack-bitmap: uninteresting oid can be outside bitmapped packfile","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:40Z","receivedAt":"2019-12-18T11:26:17Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nbitmap_has_oid_in_uninteresting() only used bitmap_position_packfile(),\nnot bitmap_position(). So it wouldn't find objects which weren't in the\nbitmapped packfile (i.e., ones where we extended the bitmap to handle\nloose objects, or objects in other packs).\n\nAs we could reuse a delta against such an object it is suboptimal not\nto use bitmap_position(), so let's use it instead of\nbitmap_position_packfile().\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n pack-bitmap.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex fb4f6297f2..de65f2fc36 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1137,7 +1137,7 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,\n \tif (!bitmap_git->haves)\n \t\treturn 0; /* walk had no \"haves\" */\n \n-\tpos = bitmap_position_packfile(bitmap_git, oid);\n+\tpos = bitmap_position(bitmap_git, oid);\n \tif (pos < 0)\n \t\treturn 0;\n \n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388429","messageId":"20191218112547.4974-7-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 06/12] pack-bitmap: simplify bitmap_has_oid_in_uninteresting()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:41Z","receivedAt":"2019-12-18T11:26:19Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nLet's refactor bitmap_has_oid_in_uninteresting() using\nbitmap_walk_contains().\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n pack-bitmap.c | 14 ++------------\n 1 file changed, 2 insertions(+), 12 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex de65f2fc36..0bbc651dde 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -1130,16 +1130,6 @@ void free_bitmap_index(struct bitmap_index *b)\n int bitmap_has_oid_in_uninteresting(struct bitmap_index *bitmap_git,\n \t\t\t\t const struct object_id *oid)\n {\n-\tint pos;\n-\n-\tif (!bitmap_git)\n-\t\treturn 0; /* no bitmap loaded */\n-\tif (!bitmap_git->haves)\n-\t\treturn 0; /* walk had no \"haves\" */\n-\n-\tpos = bitmap_position(bitmap_git, oid);\n-\tif (pos < 0)\n-\t\treturn 0;\n-\n-\treturn bitmap_get(bitmap_git->haves, pos);\n+\treturn bitmap_git &&\n+\t\tbitmap_walk_contains(bitmap_git, bitmap_git->haves, oid);\n }\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388430","messageId":"20191218112547.4974-10-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 09/12] builtin/pack-objects: introduce obj_is_packed()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:44Z","receivedAt":"2019-12-18T11:26:20Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nLet's refactor the way we check if an object is packed by\nintroducing obj_is_packed(). This function is now a simple\nwrapper around packlist_find(), but it will evolve in a\nfollowing commit.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 9 +++++++--\n 1 file changed, 7 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 801e23dfe7..43730154ba 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2553,6 +2553,11 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n \tfree(p);\n }\n \n+static int obj_is_packed(const struct object_id *oid)\n+{\n+\treturn !!packlist_find(&to_pack, oid);\n+}\n+\n static void add_tag_chain(const struct object_id *oid)\n {\n \tstruct tag *tag;\n@@ -2564,7 +2569,7 @@ static void add_tag_chain(const struct object_id *oid)\n \t * it was included via bitmaps, we would not have parsed it\n \t * previously).\n \t */\n-\tif (packlist_find(&to_pack, oid))\n+\tif (obj_is_packed(oid))\n \t\treturn;\n \n \ttag = lookup_tag(the_repository, oid);\n@@ -2588,7 +2593,7 @@ static int add_ref_tag(const char *path, const struct object_id *oid, int flag,\n \n \tif (starts_with(path, \"refs/tags/\") && /* is a tag? */\n \t !peel_ref(path, &peeled) && /* peelable? */\n-\t packlist_find(&to_pack, &peeled)) /* object packed? */\n+\t obj_is_packed(&peeled)) /* object packed? */\n \t\tadd_tag_chain(oid);\n \treturn 0;\n }\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388431","messageId":"20191218112547.4974-8-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 07/12] csum-file: introduce hashfile_total()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:42Z","receivedAt":"2019-12-18T11:26:21Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nWe will need this helper function in a following commit\nto give us total number of bytes fed to the hashfile so far.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n csum-file.h | 9 +++++++++\n 1 file changed, 9 insertions(+)\n\ndiff --git a/csum-file.h b/csum-file.h\nindex a98b1eee53..f9cbd317fb 100644\n--- a/csum-file.h\n+++ b/csum-file.h\n@@ -42,6 +42,15 @@ void hashflush(struct hashfile *f);\n void crc32_begin(struct hashfile *);\n uint32_t crc32_end(struct hashfile *);\n \n+/*\n+ * Returns the total number of bytes fed to the hashfile so far (including ones\n+ * that have not been written out to the descriptor yet).\n+ */\n+static inline off_t hashfile_total(struct hashfile *f)\n+{\n+\treturn f->total + f->offset;\n+}\n+\n static inline void hashwrite_u8(struct hashfile *f, uint8_t data)\n {\n \thashwrite(f, &data, sizeof(data));\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388432","messageId":"20191218112547.4974-9-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 08/12] pack-objects: introduce pack.allowPackReuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:43Z","receivedAt":"2019-12-18T11:26:23Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nLet's make it possible to configure if we want pack reuse or not.\n\nThe main reason it might not be wanted is probably debugging and\nperformance testing, though pack reuse _might_ cause larger packs,\nbecause we wouldn't consider the reused objects as bases for\nfinding new deltas.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Documentation/config/pack.txt | 7 +++++++\n builtin/pack-objects.c | 8 +++++++-\n 2 files changed, 14 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\nindex 1d66f0c992..0dac580581 100644\n--- a/Documentation/config/pack.txt\n+++ b/Documentation/config/pack.txt\n@@ -27,6 +27,13 @@ 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.allowPackReuse::\n+\tWhen true, and when reachability bitmaps are enabled,\n+\tpack-objects will try to send parts of the bitmapped packfile\n+\tverbatim. This can reduce memory and CPU usage to serve fetches,\n+\tbut might result in sending a slightly larger pack. Defaults to\n+\ttrue.\n+\n pack.island::\n \tAn extended regular expression configuring a set of delta\n \tislands. See \"DELTA ISLANDS\" in linkgit:git-pack-objects[1]\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 369f46fbc5..801e23dfe7 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -96,6 +96,7 @@ static off_t reuse_packfile_offset;\n \n static int use_bitmap_index_default = 1;\n static int use_bitmap_index = -1;\n+static int allow_pack_reuse = 1;\n static enum {\n \tWRITE_BITMAP_FALSE = 0,\n \tWRITE_BITMAP_QUIET,\n@@ -2699,6 +2700,10 @@ static int git_pack_config(const char *k, const char *v, void *cb)\n \t\tuse_bitmap_index_default = git_config_bool(k, v);\n \t\treturn 0;\n \t}\n+\tif (!strcmp(k, \"pack.allowpackreuse\")) {\n+\t\tallow_pack_reuse = git_config_bool(k, v);\n+\t\treturn 0;\n+\t}\n \tif (!strcmp(k, \"pack.threads\")) {\n \t\tdelta_search_threads = git_config_int(k, v);\n \t\tif (delta_search_threads < 0)\n@@ -3030,7 +3035,8 @@ static void loosen_unused_packed_objects(void)\n */\n static int pack_options_allow_reuse(void)\n {\n-\treturn pack_to_stdout &&\n+\treturn allow_pack_reuse &&\n+\t pack_to_stdout &&\n \t allow_ofs_delta &&\n \t !ignore_packed_keep_on_disk &&\n \t !ignore_packed_keep_in_core &&\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388433","messageId":"20191218112547.4974-11-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 10/12] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:45Z","receivedAt":"2019-12-18T11:26:24Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nThe old code to reuse deltas from an existing packfile\njust tried to dump a whole segment of the pack verbatim.\nThat's faster than the traditional way of actually adding\nobjects to the packing list, but it didn't kick in very\noften. This new code is really going for a middle ground:\ndo _some_ per-object work, but way less than we'd\ntraditionally do.\n\nThe general strategy of the new code is to make a bitmap\nof objects from the packfile we'll include, and then\niterate over it, writing out each object exactly as it is\nin our on-disk pack, but _not_ adding it to our packlist\n(which costs memory, and increases the search space for\ndeltas).\n\nOne complication is that if we're omitting some objects,\nwe can't set a delta against a base that we're not\nsending. So we have to check each object in\ntry_partial_reuse() to make sure we have its delta.\n\nAbout performance, in the worst case we might have\ninterleaved objects that we are sending or not sending,\nand we'd have as many chunks as objects. But in practice\nwe send big chunks.\n\nFor instance, packing torvalds/linux on GitHub servers\nnow reused 6.5M objects, but only needed ~50k chunks.\n\nHelped-by: Jonathan Tan \nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 214 ++++++++++++++++++++++++++++++++---------\n pack-bitmap.c | 150 +++++++++++++++++++++--------\n pack-bitmap.h | 3 +-\n 3 files changed, 281 insertions(+), 86 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 43730154ba..c80c1fac94 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -92,7 +92,7 @@ static struct progress *progress_state;\n \n static struct packed_git *reuse_packfile;\n static uint32_t reuse_packfile_objects;\n-static off_t reuse_packfile_offset;\n+static struct bitmap *reuse_packfile_bitmap;\n \n static int use_bitmap_index_default = 1;\n static int use_bitmap_index = -1;\n@@ -785,57 +785,185 @@ static struct object_entry **compute_write_order(void)\n \treturn wo;\n }\n \n-static off_t write_reused_pack(struct hashfile *f)\n+\n+/*\n+ * A reused set of objects. All objects in a chunk have the same\n+ * relative position in the original packfile and the generated\n+ * packfile.\n+ */\n+\n+static struct reused_chunk {\n+\t/* The offset of the first object of this chunk in the original\n+\t * packfile. */\n+\toff_t original;\n+\t/* The offset of the first object of this chunk in the generated\n+\t * packfile minus \"original\". */\n+\toff_t difference;\n+} *reused_chunks;\n+static int reused_chunks_nr;\n+static int reused_chunks_alloc;\n+\n+static void record_reused_object(off_t where, off_t offset)\n+{\n+\tif (reused_chunks_nr && reused_chunks[reused_chunks_nr-1].difference == offset)\n+\t\treturn;\n+\n+\tALLOC_GROW(reused_chunks, reused_chunks_nr + 1,\n+\t\t reused_chunks_alloc);\n+\treused_chunks[reused_chunks_nr].original = where;\n+\treused_chunks[reused_chunks_nr].difference = offset;\n+\treused_chunks_nr++;\n+}\n+\n+/*\n+ * Binary search to find the chunk that \"where\" is in. Note\n+ * that we're not looking for an exact match, just the first\n+ * chunk that contains it (which implicitly ends at the start\n+ * of the next chunk.\n+ */\n+static off_t find_reused_offset(off_t where)\n {\n-\tunsigned char buffer[8192];\n-\toff_t to_write, total;\n-\tint fd;\n+\tint lo = 0, hi = reused_chunks_nr;\n+\twhile (lo < hi) {\n+\t\tint mi = lo + ((hi - lo) / 2);\n+\t\tif (where == reused_chunks[mi].original)\n+\t\t\treturn reused_chunks[mi].difference;\n+\t\tif (where < reused_chunks[mi].original)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi + 1;\n+\t}\n \n-\tif (!is_pack_valid(reuse_packfile))\n-\t\tdie(_(\"packfile is invalid: %s\"), reuse_packfile->pack_name);\n+\t/*\n+\t * The first chunk starts at zero, so we can't have gone below\n+\t * there.\n+\t */\n+\tassert(lo);\n+\treturn reused_chunks[lo-1].difference;\n+}\n \n-\tfd = git_open(reuse_packfile->pack_name);\n-\tif (fd < 0)\n-\t\tdie_errno(_(\"unable to open packfile for reuse: %s\"),\n-\t\t\t reuse_packfile->pack_name);\n+static void write_reused_pack_one(size_t pos, struct hashfile *out,\n+\t\t\t\t struct pack_window **w_curs)\n+{\n+\toff_t offset, next, cur;\n+\tenum object_type type;\n+\tunsigned long size;\n \n-\tif (lseek(fd, sizeof(struct pack_header), SEEK_SET) == -1)\n-\t\tdie_errno(_(\"unable to seek in reused packfile\"));\n+\toffset = reuse_packfile->revindex[pos].offset;\n+\tnext = reuse_packfile->revindex[pos + 1].offset;\n \n-\tif (reuse_packfile_offset < 0)\n-\t\treuse_packfile_offset = reuse_packfile->pack_size - the_hash_algo->rawsz;\n+\trecord_reused_object(offset, offset - hashfile_total(out));\n \n-\ttotal = to_write = reuse_packfile_offset - sizeof(struct pack_header);\n+\tcur = offset;\n+\ttype = unpack_object_header(reuse_packfile, w_curs, &cur, &size);\n+\tassert(type >= 0);\n \n-\twhile (to_write) {\n-\t\tint read_pack = xread(fd, buffer, sizeof(buffer));\n+\tif (type == OBJ_OFS_DELTA) {\n+\t\toff_t base_offset;\n+\t\toff_t fixup;\n+\n+\t\tunsigned char header[MAX_PACK_OBJECT_HEADER];\n+\t\tunsigned len;\n+\n+\t\tbase_offset = get_delta_base(reuse_packfile, w_curs, &cur, type, offset);\n+\t\tassert(base_offset != 0);\n+\n+\t\t/* Convert to REF_DELTA if we must... */\n+\t\tif (!allow_ofs_delta) {\n+\t\t\tint base_pos = find_revindex_position(reuse_packfile, base_offset);\n+\t\t\tconst unsigned char *base_sha1 =\n+\t\t\t\tnth_packed_object_sha1(reuse_packfile,\n+\t\t\t\t\t\t reuse_packfile->revindex[base_pos].nr);\n+\n+\t\t\tlen = encode_in_pack_object_header(header, sizeof(header),\n+\t\t\t\t\t\t\t OBJ_REF_DELTA, size);\n+\t\t\thashwrite(out, header, len);\n+\t\t\thashwrite(out, base_sha1, 20);\n+\t\t\tcopy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);\n+\t\t\treturn;\n+\t\t}\n \n-\t\tif (read_pack <= 0)\n-\t\t\tdie_errno(_(\"unable to read from reused packfile\"));\n+\t\t/* Otherwise see if we need to rewrite the offset... */\n+\t\tfixup = find_reused_offset(offset) -\n+\t\t\tfind_reused_offset(base_offset);\n+\t\tif (fixup) {\n+\t\t\tunsigned char ofs_header[10];\n+\t\t\tunsigned i, ofs_len;\n+\t\t\toff_t ofs = offset - base_offset - fixup;\n \n-\t\tif (read_pack > to_write)\n-\t\t\tread_pack = to_write;\n+\t\t\tlen = encode_in_pack_object_header(header, sizeof(header),\n+\t\t\t\t\t\t\t OBJ_OFS_DELTA, size);\n \n-\t\thashwrite(f, buffer, read_pack);\n-\t\tto_write -= read_pack;\n+\t\t\ti = sizeof(ofs_header) - 1;\n+\t\t\tofs_header[i] = ofs & 127;\n+\t\t\twhile (ofs >>= 7)\n+\t\t\t\tofs_header[--i] = 128 | (--ofs & 127);\n+\n+\t\t\tofs_len = sizeof(ofs_header) - i;\n+\n+\t\t\thashwrite(out, header, len);\n+\t\t\thashwrite(out, ofs_header + sizeof(ofs_header) - ofs_len, ofs_len);\n+\t\t\tcopy_pack_data(out, reuse_packfile, w_curs, cur, next - cur);\n+\t\t\treturn;\n+\t\t}\n+\n+\t\t/* ...otherwise we have no fixup, and can write it verbatim */\n+\t}\n+\n+\tcopy_pack_data(out, reuse_packfile, w_curs, offset, next - offset);\n+}\n+\n+static size_t write_reused_pack_verbatim(struct hashfile *out,\n+\t\t\t\t\t struct pack_window **w_curs)\n+{\n+\tsize_t pos = 0;\n+\n+\twhile (pos < reuse_packfile_bitmap->word_alloc &&\n+\t\t\treuse_packfile_bitmap->words[pos] == (eword_t)~0)\n+\t\tpos++;\n+\n+\tif (pos) {\n+\t\toff_t to_write;\n+\n+\t\twritten = (pos * BITS_IN_EWORD);\n+\t\tto_write = reuse_packfile->revindex[written].offset\n+\t\t\t- sizeof(struct pack_header);\n+\n+\t\t/* We're recording one chunk, not one object. */\n+\t\trecord_reused_object(sizeof(struct pack_header), 0);\n+\t\thashflush(out);\n+\t\tcopy_pack_data(out, reuse_packfile, w_curs,\n+\t\t\tsizeof(struct pack_header), to_write);\n \n-\t\t/*\n-\t\t * We don't know the actual number of objects written,\n-\t\t * only how many bytes written, how many bytes total, and\n-\t\t * how many objects total. So we can fake it by pretending all\n-\t\t * objects we are writing are the same size. This gives us a\n-\t\t * smooth progress meter, and at the end it matches the true\n-\t\t * answer.\n-\t\t */\n-\t\twritten = reuse_packfile_objects *\n-\t\t\t\t(((double)(total - to_write)) / total);\n \t\tdisplay_progress(progress_state, written);\n \t}\n+\treturn pos;\n+}\n+\n+static void write_reused_pack(struct hashfile *f)\n+{\n+\tsize_t i = 0;\n+\tuint32_t offset;\n+\tstruct pack_window *w_curs = NULL;\n+\n+\tif (allow_ofs_delta)\n+\t\ti = write_reused_pack_verbatim(f, &w_curs);\n+\n+\tfor (; i < reuse_packfile_bitmap->word_alloc; ++i) {\n+\t\teword_t word = reuse_packfile_bitmap->words[i];\n+\t\tsize_t pos = (i * BITS_IN_EWORD);\n+\n+\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n+\t\t\tif ((word >> offset) == 0)\n+\t\t\t\tbreak;\n+\n+\t\t\toffset += ewah_bit_ctz64(word >> offset);\n+\t\t\twrite_reused_pack_one(pos + offset, f, &w_curs);\n+\t\t\tdisplay_progress(progress_state, ++written);\n+\t\t}\n+\t}\n \n-\tclose(fd);\n-\twritten = reuse_packfile_objects;\n-\tdisplay_progress(progress_state, written);\n-\treturn reuse_packfile_offset - sizeof(struct pack_header);\n+\tunuse_pack(&w_curs);\n }\n \n static const char no_split_warning[] = N_(\n@@ -868,11 +996,9 @@ static void write_pack_file(void)\n \t\toffset = write_pack_header(f, nr_remaining);\n \n \t\tif (reuse_packfile) {\n-\t\t\toff_t packfile_size;\n \t\t\tassert(pack_to_stdout);\n-\n-\t\t\tpackfile_size = write_reused_pack(f);\n-\t\t\toffset += packfile_size;\n+\t\t\twrite_reused_pack(f);\n+\t\t\toffset = hashfile_total(f);\n \t\t}\n \n \t\tnr_written = 0;\n@@ -2661,6 +2787,7 @@ static void prepare_pack(int window, int depth)\n \n \tif (nr_deltas && n > 1) {\n \t\tunsigned nr_done = 0;\n+\n \t\tif (progress)\n \t\t\tprogress_state = start_progress(_(\"Compressing objects\"),\n \t\t\t\t\t\t\tnr_deltas);\n@@ -3042,7 +3169,6 @@ static int pack_options_allow_reuse(void)\n {\n \treturn allow_pack_reuse &&\n \t pack_to_stdout &&\n-\t allow_ofs_delta &&\n \t !ignore_packed_keep_on_disk &&\n \t !ignore_packed_keep_in_core &&\n \t (!local || !have_non_local_packs) &&\n@@ -3059,7 +3185,7 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n \t\t\tbitmap_git,\n \t\t\t&reuse_packfile,\n \t\t\t&reuse_packfile_objects,\n-\t\t\t&reuse_packfile_offset)) {\n+\t\t\t&reuse_packfile_bitmap)) {\n \t\tassert(reuse_packfile_objects);\n \t\tnr_result += reuse_packfile_objects;\n \t\tdisplay_progress(progress_state, nr_result);\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex 0bbc651dde..a1d43d367a 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -326,6 +326,13 @@ static int load_pack_bitmap(struct bitmap_index *bitmap_git)\n \tmunmap(bitmap_git->map, bitmap_git->map_size);\n \tbitmap_git->map = NULL;\n \tbitmap_git->map_size = 0;\n+\n+\tkh_destroy_oid_map(bitmap_git->bitmaps);\n+\tbitmap_git->bitmaps = NULL;\n+\n+\tkh_destroy_oid_pos(bitmap_git->ext_index.positions);\n+\tbitmap_git->ext_index.positions = NULL;\n+\n \treturn -1;\n }\n \n@@ -768,65 +775,126 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \treturn NULL;\n }\n \n-int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n-\t\t\t\t struct packed_git **packfile,\n-\t\t\t\t uint32_t *entries,\n-\t\t\t\t off_t *up_to)\n+static void try_partial_reuse(struct bitmap_index *bitmap_git,\n+\t\t\t size_t pos,\n+\t\t\t struct bitmap *reuse,\n+\t\t\t struct pack_window **w_curs)\n {\n+\tstruct revindex_entry *revidx;\n+\toff_t offset;\n+\tenum object_type type;\n+\tunsigned long size;\n+\n+\tif (pos >= bitmap_git->pack->num_objects)\n+\t\treturn; /* not actually in the pack */\n+\n+\trevidx = &bitmap_git->pack->revindex[pos];\n+\toffset = revidx->offset;\n+\ttype = unpack_object_header(bitmap_git->pack, w_curs, &offset, &size);\n+\tif (type < 0)\n+\t\treturn; /* broken packfile, punt */\n+\n+\tif (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {\n+\t\toff_t base_offset;\n+\t\tint base_pos;\n+\n+\t\t/*\n+\t\t * Find the position of the base object so we can look it up\n+\t\t * in our bitmaps. If we can't come up with an offset, or if\n+\t\t * that offset is not in the revidx, the pack is corrupt.\n+\t\t * There's nothing we can do, so just punt on this object,\n+\t\t * and the normal slow path will complain about it in\n+\t\t * more detail.\n+\t\t */\n+\t\tbase_offset = get_delta_base(bitmap_git->pack, w_curs,\n+\t\t\t\t\t &offset, type, revidx->offset);\n+\t\tif (!base_offset)\n+\t\t\treturn;\n+\t\tbase_pos = find_revindex_position(bitmap_git->pack, base_offset);\n+\t\tif (base_pos < 0)\n+\t\t\treturn;\n+\n+\t\t/*\n+\t\t * We assume delta dependencies always point backwards. This\n+\t\t * lets us do a single pass, and is basically always true\n+\t\t * due to the way OFS_DELTAs work. You would not typically\n+\t\t * find REF_DELTA in a bitmapped pack, since we only bitmap\n+\t\t * packs we write fresh, and OFS_DELTA is the default). But\n+\t\t * let's double check to make sure the pack wasn't written with\n+\t\t * odd parameters.\n+\t\t */\n+\t\tif (base_pos >= pos)\n+\t\t\treturn;\n+\n+\t\t/*\n+\t\t * And finally, if we're not sending the base as part of our\n+\t\t * reuse chunk, then don't send this object either. The base\n+\t\t * would come after us, along with other objects not\n+\t\t * necessarily in the pack, which means we'd need to convert\n+\t\t * to REF_DELTA on the fly. Better to just let the normal\n+\t\t * object_entry code path handle it.\n+\t\t */\n+\t\tif (!bitmap_get(reuse, base_pos))\n+\t\t\treturn;\n+\t}\n+\n \t/*\n-\t * Reuse the packfile content if we need more than\n-\t * 90% of its objects\n+\t * If we got here, then the object is OK to reuse. Mark it.\n \t */\n-\tstatic const double REUSE_PERCENT = 0.9;\n+\tbitmap_set(reuse, pos);\n+}\n \n+int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t struct packed_git **packfile_out,\n+\t\t\t\t uint32_t *entries,\n+\t\t\t\t struct bitmap **reuse_out)\n+{\n \tstruct bitmap *result = bitmap_git->result;\n-\tuint32_t reuse_threshold;\n-\tuint32_t i, reuse_objects = 0;\n+\tstruct bitmap *reuse;\n+\tstruct pack_window *w_curs = NULL;\n+\tsize_t i = 0;\n+\tuint32_t offset;\n \n \tassert(result);\n \n-\tfor (i = 0; i < result->word_alloc; ++i) {\n-\t\tif (result->words[i] != (eword_t)~0) {\n-\t\t\treuse_objects += ewah_bit_ctz64(~result->words[i]);\n-\t\t\tbreak;\n-\t\t}\n+\twhile (i < result->word_alloc && result->words[i] == (eword_t)~0)\n+\t\ti++;\n \n-\t\treuse_objects += BITS_IN_EWORD;\n-\t}\n+\t/* Don't mark objects not in the packfile */\n+\tif (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)\n+\t\ti = bitmap_git->pack->num_objects / BITS_IN_EWORD;\n \n-#ifdef GIT_BITMAP_DEBUG\n-\t{\n-\t\tconst unsigned char *sha1;\n-\t\tstruct revindex_entry *entry;\n+\treuse = bitmap_word_alloc(i);\n+\tmemset(reuse->words, 0xFF, i * sizeof(eword_t));\n \n-\t\tentry = &bitmap_git->reverse_index->revindex[reuse_objects];\n-\t\tsha1 = nth_packed_object_sha1(bitmap_git->pack, entry->nr);\n-\n-\t\tfprintf(stderr, \"Failed to reuse at %d (%016llx)\\n\",\n-\t\t\treuse_objects, result->words[i]);\n-\t\tfprintf(stderr, \" %s\\n\", hash_to_hex(sha1));\n-\t}\n-#endif\n+\tfor (; i < result->word_alloc; ++i) {\n+\t\teword_t word = result->words[i];\n+\t\tsize_t pos = (i * BITS_IN_EWORD);\n \n-\tif (!reuse_objects)\n-\t\treturn -1;\n+\t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n+\t\t\tif ((word >> offset) == 0)\n+\t\t\t\tbreak;\n \n-\tif (reuse_objects >= bitmap_git->pack->num_objects) {\n-\t\tbitmap_git->reuse_objects = *entries = bitmap_git->pack->num_objects;\n-\t\t*up_to = -1; /* reuse the full pack */\n-\t\t*packfile = bitmap_git->pack;\n-\t\treturn 0;\n+\t\t\toffset += ewah_bit_ctz64(word >> offset);\n+\t\t\ttry_partial_reuse(bitmap_git, pos + offset, reuse, &w_curs);\n+\t\t}\n \t}\n \n-\treuse_threshold = bitmap_popcount(bitmap_git->result) * REUSE_PERCENT;\n+\tunuse_pack(&w_curs);\n \n-\tif (reuse_objects < reuse_threshold)\n+\t*entries = bitmap_popcount(reuse);\n+\tif (!*entries) {\n+\t\tbitmap_free(reuse);\n \t\treturn -1;\n+\t}\n \n-\tbitmap_git->reuse_objects = *entries = reuse_objects;\n-\t*up_to = bitmap_git->pack->revindex[reuse_objects].offset;\n-\t*packfile = bitmap_git->pack;\n-\n+\t/*\n+\t * Drop any reused objects from the result, since they will not\n+\t * need to be handled separately.\n+\t */\n+\tbitmap_and_not(result, reuse);\n+\t*packfile_out = bitmap_git->pack;\n+\t*reuse_out = reuse;\n \treturn 0;\n }\n \ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 6ab6033dbe..bcd03b8993 100644\n--- a/pack-bitmap.h\n+++ b/pack-bitmap.h\n@@ -50,7 +50,8 @@ void test_bitmap_walk(struct rev_info *revs);\n struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs);\n int reuse_partial_packfile_from_bitmap(struct bitmap_index *,\n \t\t\t\t struct packed_git **packfile,\n-\t\t\t\t uint32_t *entries, off_t *up_to);\n+\t\t\t\t uint32_t *entries,\n+\t\t\t\t struct bitmap **reuse_out);\n int rebuild_existing_bitmaps(struct bitmap_index *, struct packing_data *mapping,\n \t\t\t kh_oid_map_t *reused_bitmaps, int show_progress);\n void free_bitmap_index(struct bitmap_index *);\n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388434","messageId":"20191218112547.4974-13-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 12/12] pack-bitmap: don't rely on bitmap_git->reuse_objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:47Z","receivedAt":"2019-12-18T11:26:25Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nWe no longer compute bitmap_git->reuse_objects, so we\ncannot rely on it anymore to terminate the loop early;\nwe have to iterate to the end.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n pack-bitmap.c | 18 +++++++-----------\n 1 file changed, 7 insertions(+), 11 deletions(-)\n\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex a1d43d367a..5a8689cdf8 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -629,7 +629,7 @@ static void show_objects_for_type(\n \tenum object_type object_type,\n \tshow_reachable_fn show_reach)\n {\n-\tsize_t pos = 0, i = 0;\n+\tsize_t i = 0;\n \tuint32_t offset;\n \n \tstruct ewah_iterator it;\n@@ -637,13 +637,15 @@ static void show_objects_for_type(\n \n \tstruct bitmap *objects = bitmap_git->result;\n \n-\tif (bitmap_git->reuse_objects == bitmap_git->pack->num_objects)\n-\t\treturn;\n-\n \tewah_iterator_init(&it, type_filter);\n \n-\twhile (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {\n+\tfor (i = 0; i < objects->word_alloc &&\n+\t\t\tewah_iterator_next(&filter, &it); i++) {\n \t\teword_t word = objects->words[i] & filter;\n+\t\tsize_t pos = (i * BITS_IN_EWORD);\n+\n+\t\tif (!word)\n+\t\t\tcontinue;\n \n \t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n \t\t\tstruct object_id oid;\n@@ -655,9 +657,6 @@ static void show_objects_for_type(\n \n \t\t\toffset += ewah_bit_ctz64(word >> offset);\n \n-\t\t\tif (pos + offset < bitmap_git->reuse_objects)\n-\t\t\t\tcontinue;\n-\n \t\t\tentry = &bitmap_git->pack->revindex[pos + offset];\n \t\t\tnth_packed_object_oid(&oid, bitmap_git->pack, entry->nr);\n \n@@ -666,9 +665,6 @@ static void show_objects_for_type(\n \n \t\t\tshow_reach(&oid, object_type, 0, hash, bitmap_git->pack, entry->offset);\n \t\t}\n-\n-\t\tpos += BITS_IN_EWORD;\n-\t\ti++;\n \t}\n }\n \n-- \n2.24.1.498.g561400140f\n\n"},{"id":"388435","messageId":"20191218112547.4974-12-chriscool@tuxfamily.org","threadId":"52480","inReplyTo":"20191218112547.4974-1-chriscool@tuxfamily.org","subject":"[PATCH v4 11/12] pack-objects: add checks for duplicate objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-12-18T11:25:46Z","receivedAt":"2019-12-18T11:26:26Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nAdditional checks are added in have_duplicate_entry() and\nobj_is_packed() to avoid duplicate objects in the reuse\nbitmap. It was probably buggy to not have such a check\nbefore.\n\nGit as a client would never both asks for a tag by sha1 and\nspecify \"include-tag\", but libgit2 will, so a libgit2 client\ncloning from a Git server would trigger the bug.\n\nIf a client both asks for a tag by sha1 and specifies\n\"include-tag\", we may end up including the tag in the reuse\nbitmap (due to the first thing), and then later adding it to\nthe packlist (due to the second). This results in duplicate\nobjects in the pack, which git chokes on. We should notice\nthat we are already including it when doing the include-tag\nportion, and avoid adding it to the packlist.\n\nThe simplest place to fix this is right in add_ref_tag(),\nwhere we could avoid peeling the tag at all if we know that\nwe are already including it. However, this pushes the check\ninstead into have_duplicate_entry(). This fixes not only\nthis case, but also means that we cannot have any similar\nproblems lurking in other code.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 8 +++++++-\n 1 file changed, 7 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c80c1fac94..b1998202fb 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -1127,6 +1127,10 @@ static int have_duplicate_entry(const struct object_id *oid,\n {\n \tstruct object_entry *entry;\n \n+\tif (reuse_packfile_bitmap &&\n+\t bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid))\n+\t\treturn 1;\n+\n \tentry = packlist_find(&to_pack, oid);\n \tif (!entry)\n \t\treturn 0;\n@@ -2681,7 +2685,9 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,\n \n static int obj_is_packed(const struct object_id *oid)\n {\n-\treturn !!packlist_find(&to_pack, oid);\n+\treturn packlist_find(&to_pack, oid) ||\n+\t\t(reuse_packfile_bitmap &&\n+\t\t bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));\n }\n \n static void add_tag_chain(const struct object_id *oid)\n-- \n2.24.1.498.g561400140f\n\n"}]}