{"thread":{"id":"52072","subject":"[PATCH v2 0/9] Rewrite packfile reuse code","startedAt":"2019-10-19T10:35:53Z","lastAt":"2019-10-26T09:34:32Z","messageCount":22,"participants":["Christian Couder","Philip Oakley","Jeff King","Jonathan Tan"],"isPatch":true,"patchVersion":2,"patchTotal":9},"messages":[{"id":"384442","messageId":"20191019103531.23274-1-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":null,"subject":"[PATCH v2 0/9] Rewrite packfile reuse code","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:22Z","receivedAt":"2019-10-19T10:35:53Z","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 version of this patch series was also discussed:\n\nhttps://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\nChanges since the previous patch series are the following:\n\n - Rebased onto current master (v2.24.0-rc0), which means that\n conflicts due to dropping the last argument of packlist_find() are\n resolved.\n\n - Replaced \"in a following patch\" with \"in a following commit\" in\n commit messages.\n\n - Squashed previous patchs 3/10 and 4/10 into new patch 3/9 as\n suggested by Peff and Jonathan.\n\n - Changed commit message of patch 3/9, so that the justification\n should be correct now.\n\n - Also in patch 3/9, `block ? block * 2 : 1` is now used to compute\n the number of words that should be allocated.\n\n - Changed commit message of patch 4/9 (previously 5/10), so that the\n justification should be correct now.\n\n - Document pack.allowPackReuse in patch 7/9.\n\n - Also in patch 7/9 move using the `allow_pack_reuse` variable into\n pack_options_allow_reuse() as suggested by Junio.\n\n - Improved commit message in patch 9/9 a lot by adding many comments\n made by Peff about it.\n\n - In patch 9/9 removed `if (0) { ... }` code.\n\n - Also in patch 9/9 changed parameter name from\n `struct bitmap **bitmap` to `struct bitmap **reuse_out` in\n pack-bitmap.h as suggested by Jonathan.\n\nI tried to use `git range-diff` to see if I could send its output to\ncompare this patch series with the previous one, but it looks like it\nunfortunately thinks that new patch 7/9 is completely different than\nprevious patch 8/10, and also it shows a lot more changes from patch\n10/10 to patch 9/9 than necessary for some reason. So I decided not to\nsend it, but if you want it anyway please tell me.\n\nI have put Peff as the author of all the commits.\n\nJeff King (9):\n builtin/pack-objects: report reused packfile objects\n packfile: expose get_delta_base()\n ewah/bitmap: introduce bitmap_word_alloc()\n pack-bitmap: don't rely on bitmap_git->reuse_objects\n pack-bitmap: introduce bitmap_walk_contains()\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\n Documentation/config/pack.txt | 4 +\n builtin/pack-objects.c | 235 +++++++++++++++++++++++++++-------\n csum-file.h | 9 ++\n ewah/bitmap.c | 13 +-\n ewah/ewok.h | 1 +\n pack-bitmap.c | 178 +++++++++++++++++--------\n pack-bitmap.h | 6 +-\n packfile.c | 10 +-\n packfile.h | 3 +\n 9 files changed, 349 insertions(+), 110 deletions(-)\n\n-- \n2.24.0.rc0.9.gef620577e2\n\n"},{"id":"384443","messageId":"20191019103531.23274-2-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 1/9] builtin/pack-objects: report reused packfile objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:23Z","receivedAt":"2019-10-19T10:35:54Z","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 5876583220..f2c2703090 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.0.rc0.9.gef620577e2\n\n"},{"id":"384444","messageId":"20191019103531.23274-3-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 2/9] packfile: expose get_delta_base()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:24Z","receivedAt":"2019-10-19T10:35:58Z","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.0.rc0.9.gef620577e2\n\n"},{"id":"384445","messageId":"20191019103531.23274-4-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 3/9] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:25Z","receivedAt":"2019-10-19T10:35:58Z","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\nWe will also always access at least one word for each bitmap,\nso we want to make sure that at least one is always\nallocated.\n\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.0.rc0.9.gef620577e2\n\n"},{"id":"384446","messageId":"20191019103531.23274-5-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 4/9] pack-bitmap: don't rely on bitmap_git->reuse_objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:26Z","receivedAt":"2019-10-19T10:35:58Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nWe will no longer compute bitmap_git->reuse_objects in a\nfollowing commit, so we cannot rely on it anymore to\nterminate the loop early; we 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 e07c798879..016d0319fc 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -622,7 +622,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@@ -630,13 +630,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@@ -648,9 +650,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@@ -659,9 +658,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.0.rc0.9.gef620577e2\n\n"},{"id":"384447","messageId":"20191019103531.23274-6-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 5/9] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:27Z","receivedAt":"2019-10-19T10:36:02Z","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 016d0319fc..8a51302a1a 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -826,6 +826,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.0.rc0.9.gef620577e2\n\n"},{"id":"384448","messageId":"20191019103531.23274-7-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 6/9] csum-file: introduce hashfile_total()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:28Z","receivedAt":"2019-10-19T10:36:02Z","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.0.rc0.9.gef620577e2\n\n"},{"id":"384450","messageId":"20191019103531.23274-8-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 7/9] pack-objects: introduce pack.allowPackReuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:29Z","receivedAt":"2019-10-19T10:36:04Z","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\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n Documentation/config/pack.txt | 4 ++++\n builtin/pack-objects.c | 8 +++++++-\n 2 files changed, 11 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/config/pack.txt b/Documentation/config/pack.txt\nindex 1d66f0c992..58323a351f 100644\n--- a/Documentation/config/pack.txt\n+++ b/Documentation/config/pack.txt\n@@ -27,6 +27,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.allowPackReuse::\n+\tWhen true, which is the default, Git will try to reuse parts\n+\tof existing packfiles when preparing new packfiles.\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 f2c2703090..4fcfcf6097 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.0.rc0.9.gef620577e2\n\n"},{"id":"384449","messageId":"20191019103531.23274-9-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 8/9] builtin/pack-objects: introduce obj_is_packed()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:30Z","receivedAt":"2019-10-19T10:36:05Z","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 4fcfcf6097..08898331ef 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.0.rc0.9.gef620577e2\n\n"},{"id":"384451","messageId":"20191019103531.23274-10-chriscool@tuxfamily.org","threadId":"52072","inReplyTo":"20191019103531.23274-1-chriscool@tuxfamily.org","subject":"[PATCH v2 9/9] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T10:35:31Z","receivedAt":"2019-10-19T10:36:08Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nLet's store the chunks of the packfile that we reuse in\na dynamic array of `struct reused_chunk`, and let's use\na reuse_packfile_bitmap to speed up reusing parts of\npackfiles.\n\nThe dynamic array of `struct reused_chunk` is useful\nbecause we need to know not just the number of zero bits,\nbut the accumulated offset due to missing objects. So\nwithout the array we'd end up having to walk over the\nrevindex for that set of objects. The array is\nbasically caching those accumulated offsets (for the\nparts we _do_ include), so we don't have to compute them\nrepeatedly.\n\nThe old code just tried to dump a whole segment of the\npack verbatim. That's faster than the traditional way of\nactually adding objects to the packing list, but it\ndidn't kick in very often. This new code is really going\nfor a middle ground: do _some_ per-object work, but way\nless than we'd traditionally do.\n\nFor instance, packing torvalds/linux on GitHub servers\njust now reused 6.5M objects, but only needed ~50k\nchunks.\n\nAdditional checks are added in have_duplicate_entry()\nand obj_is_packed() to avoid duplicate objects in the\nreuse bitmap. It was probably buggy to not have such a\ncheck before.\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, I've pushed 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\nNo tests, because git does not actually exhibit this \"ask\nfor it and also include-tag\" behavior. We do one or the\nother on clone, depending on whether --single-branch is set.\nHowever, libgit2 does both.\n\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, 280 insertions(+), 87 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 08898331ef..f710f8dde3 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,177 @@ 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+ * Record the offsets needed in our reused packfile chunks due to\n+ * \"gaps\" where we omitted some objects.\n+ */\n+static struct reused_chunk {\n+\toff_t start;\n+\toff_t offset;\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-\tunsigned char buffer[8192];\n-\toff_t to_write, total;\n-\tint fd;\n+\tif (reused_chunks_nr && reused_chunks[reused_chunks_nr-1].offset == offset)\n+\t\treturn;\n \n-\tif (!is_pack_valid(reuse_packfile))\n-\t\tdie(_(\"packfile is invalid: %s\"), reuse_packfile->pack_name);\n+\tALLOC_GROW(reused_chunks, reused_chunks_nr + 1,\n+\t\t reused_chunks_alloc);\n+\treused_chunks[reused_chunks_nr].start = where;\n+\treused_chunks[reused_chunks_nr].offset = offset;\n+\treused_chunks_nr++;\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+/*\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+\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].start)\n+\t\t\treturn reused_chunks[mi].offset;\n+\t\tif (where < reused_chunks[mi].start)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi + 1;\n+\t}\n \n-\tif (lseek(fd, sizeof(struct pack_header), SEEK_SET) == -1)\n-\t\tdie_errno(_(\"unable to seek in reused packfile\"));\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].offset;\n+}\n+\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+\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\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 +988,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@@ -1001,6 +1119,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@@ -2555,7 +2677,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@@ -2661,6 +2785,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 +3167,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 +3183,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 8a51302a1a..cbfc544411 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@@ -764,65 +771,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-\n-\t\treuse_objects += BITS_IN_EWORD;\n-\t}\n+\twhile (i < result->word_alloc && result->words[i] == (eword_t)~0)\n+\t\ti++;\n \n-#ifdef GIT_BITMAP_DEBUG\n-\t{\n-\t\tconst unsigned char *sha1;\n-\t\tstruct revindex_entry *entry;\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-\t\tentry = &bitmap_git->reverse_index->revindex[reuse_objects];\n-\t\tsha1 = nth_packed_object_sha1(bitmap_git->pack, entry->nr);\n+\treuse = bitmap_word_alloc(i);\n+\tmemset(reuse->words, 0xFF, i * sizeof(eword_t));\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.0.rc0.9.gef620577e2\n\n"},{"id":"384454","messageId":"dce8e0b5-c4ea-f4f6-6275-1322f2d7200b@iee.email","threadId":"52072","inReplyTo":"20191019103531.23274-6-chriscool@tuxfamily.org","subject":"Re: [PATCH v2 5/9] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2019-10-19T15:25:19Z","receivedAt":"2019-10-19T15:25:23Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Christian,\ncan I check one thing?\n\nOn 19/10/2019 11:35, Christian Couder wrote:\n> From: Jeff King \n>\n> We will use this helper function in a following commit to\n> tell us if an object is packed.\n>\n> Signed-off-by: Jeff King \n> Signed-off-by: Christian Couder \n> ---\n> pack-bitmap.c | 12 ++++++++++++\n> pack-bitmap.h | 3 +++\n> 2 files changed, 15 insertions(+)\n>\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index 016d0319fc..8a51302a1a 100644\n> --- a/pack-bitmap.c\n> +++ b/pack-bitmap.c\n> @@ -826,6 +826,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;\nExcuse my ignorance here...\n\nFor the case on Windows (int/long 32 bit), is this return value \nguaranteed to be less than 2GiB, i.e. not a memory offset?\n\nI'm just thinking ahead to the resolution of the 4GiB file limit issue \non Git-for-Windows (https://github.com/git-for-windows/git/pull/2179)\n\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> {\n> diff --git a/pack-bitmap.h b/pack-bitmap.h\n> index 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-- \nPhilip\n"},{"id":"384455","messageId":"6e4ad9bb-20d7-4ae5-8768-326f5c455c3c@iee.email","threadId":"52072","inReplyTo":"20191019103531.23274-10-chriscool@tuxfamily.org","subject":"Re: [PATCH v2 9/9] pack-objects: improve partial packfile reuse","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2019-10-19T15:30:32Z","receivedAt":"2019-10-19T15:33:48Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Christian,\n\na couple of mem_size questions?\n\nOn 19/10/2019 11:35, Christian Couder wrote:\n> From: Jeff King \n>\n> Let's store the chunks of the packfile that we reuse in\n> a dynamic array of `struct reused_chunk`, and let's use\n> a reuse_packfile_bitmap to speed up reusing parts of\n> packfiles.\n>\n> The dynamic array of `struct reused_chunk` is useful\n> because we need to know not just the number of zero bits,\n> but the accumulated offset due to missing objects. So\n> without the array we'd end up having to walk over the\n> revindex for that set of objects. The array is\n> basically caching those accumulated offsets (for the\n> parts we _do_ include), so we don't have to compute them\n> repeatedly.\n>\n> The old code just tried to dump a whole segment of the\n> pack verbatim. That's faster than the traditional way of\n> actually adding objects to the packing list, but it\n> didn't kick in very often. This new code is really going\n> for a middle ground: do _some_ per-object work, but way\n> less than we'd traditionally do.\n>\n> For instance, packing torvalds/linux on GitHub servers\n> just now reused 6.5M objects, but only needed ~50k\n> chunks.\n>\n> Additional checks are added in have_duplicate_entry()\n> and obj_is_packed() to avoid duplicate objects in the\n> reuse bitmap. It was probably buggy to not have such a\n> check before.\n>\n> If a client both asks for a tag by sha1 and specifies\n> \"include-tag\", we may end up including the tag in the reuse\n> bitmap (due to the first thing), and then later adding it to\n> the packlist (due to the second). This results in duplicate\n> objects in the pack, which git chokes on. We should notice\n> that we are already including it when doing the include-tag\n> portion, and avoid adding it to the packlist.\n>\n> The simplest place to fix this is right in add_ref_tag,\n> where we could avoid peeling the tag at all if we know that\n> we are already including it. However, I've pushed the check\n> instead into have_duplicate_entry(). This fixes not only\n> this case, but also means that we cannot have any similar\n> problems lurking in other code.\n>\n> No tests, because git does not actually exhibit this \"ask\n> for it and also include-tag\" behavior. We do one or the\n> other on clone, depending on whether --single-branch is set.\n> However, libgit2 does both.\n>\n> Signed-off-by: Jeff King \n> Signed-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, 280 insertions(+), 87 deletions(-)\n>\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index 08898331ef..f710f8dde3 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,177 @@ 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> + * Record the offsets needed in our reused packfile chunks due to\n> + * \"gaps\" where we omitted some objects.\n> + */\n> +static struct reused_chunk {\n> +\toff_t start;\n> +\toff_t offset;\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> -\tunsigned char buffer[8192];\n> -\toff_t to_write, total;\n> -\tint fd;\n> +\tif (reused_chunks_nr && reused_chunks[reused_chunks_nr-1].offset == offset)\n> +\t\treturn;\n> \n> -\tif (!is_pack_valid(reuse_packfile))\n> -\t\tdie(_(\"packfile is invalid: %s\"), reuse_packfile->pack_name);\n> +\tALLOC_GROW(reused_chunks, reused_chunks_nr + 1,\n> +\t\t reused_chunks_alloc);\n> +\treused_chunks[reused_chunks_nr].start = where;\n> +\treused_chunks[reused_chunks_nr].offset = offset;\n> +\treused_chunks_nr++;\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> +/*\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> +\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].start)\n> +\t\t\treturn reused_chunks[mi].offset;\n> +\t\tif (where < reused_chunks[mi].start)\n> +\t\t\thi = mi;\n> +\t\telse\n> +\t\t\tlo = mi + 1;\n> +\t}\n> \n> -\tif (lseek(fd, sizeof(struct pack_header), SEEK_SET) == -1)\n> -\t\tdie_errno(_(\"unable to seek in reused packfile\"));\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].offset;\n> +}\n> +\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\nIs this a mem_sized size or a counter for less that 4GiB items?\n\n> +\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\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 +988,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> @@ -1001,6 +1119,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> @@ -2555,7 +2677,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> @@ -2661,6 +2785,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 +3167,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 +3183,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);\n> diff --git a/pack-bitmap.c b/pack-bitmap.c\n> index 8a51302a1a..cbfc544411 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> @@ -764,65 +771,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;\nIs this mem_sized or a <4GiB 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> -\n> -\t\treuse_objects += BITS_IN_EWORD;\n> -\t}\n> +\twhile (i < result->word_alloc && result->words[i] == (eword_t)~0)\n> +\t\ti++;\n> \n> -#ifdef GIT_BITMAP_DEBUG\n> -\t{\n> -\t\tconst unsigned char *sha1;\n> -\t\tstruct revindex_entry *entry;\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> -\t\tentry = &bitmap_git->reverse_index->revindex[reuse_objects];\n> -\t\tsha1 = nth_packed_object_sha1(bitmap_git->pack, entry->nr);\n> +\treuse = bitmap_word_alloc(i);\n> +\tmemset(reuse->words, 0xFF, i * sizeof(eword_t));\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> \n> diff --git a/pack-bitmap.h b/pack-bitmap.h\n> index 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 *);\nApologies if these are dumb queries..\nPhilip\n"},{"id":"384456","messageId":"CAP8UFD2dLPguCnUhTu+F4SNPxFZ7YT5io0qXkVwvSNP-sA8Jxg@mail.gmail.com","threadId":"52072","inReplyTo":"dce8e0b5-c4ea-f4f6-6275-1322f2d7200b@iee.email","subject":"Re: [PATCH v2 5/9] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T18:55:56Z","receivedAt":"2019-10-19T18:56:10Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi Philip,\n\nOn Sat, Oct 19, 2019 at 5:25 PM Philip Oakley wrote:\n>\n> Hi Christian,\n> can I check one thing?\n\nYeah, sure! Thanks for taking a look at my patches!\n\n> On 19/10/2019 11:35, Christian Couder wrote:\n\n> > +int bitmap_walk_contains(struct bitmap_index *bitmap_git,\n> > + struct bitmap *bitmap, const struct object_id *oid)\n> > +{\n> > + int idx;\n> Excuse my ignorance here...\n>\n> For the case on Windows (int/long 32 bit), is this return value\n> guaranteed to be less than 2GiB, i.e. not a memory offset?\n>\n> I'm just thinking ahead to the resolution of the 4GiB file limit issue\n> on Git-for-Windows (https://github.com/git-for-windows/git/pull/2179)\n\nI understand your concern, unfortunately, below we have:\n\nidx = bitmap_position(bitmap_git, oid);\n\nand bitmap_position() returns an int at least since 3ae5fa0768\n(pack-bitmap: remove bitmap_git global variable, 2018-06-07)\n\nSo I think the fix would be much more involved than just changing the\ntype of the idx variable. It would likely involve modifying\nbitmap_position(), and thus would probably best be addressed in a\nseparate patch series.\n\n> > +\n> > + if (!bitmap)\n> > + return 0;\n> > +\n> > + idx = bitmap_position(bitmap_git, oid);\n> > + return idx >= 0 && bitmap_get(bitmap, idx);\n> > +}\n"},{"id":"384457","messageId":"CAP8UFD2rsZj3=KoPCEWw2sTXFhNkynrJLeAGWK2vEbD5GU8chA@mail.gmail.com","threadId":"52072","inReplyTo":"6e4ad9bb-20d7-4ae5-8768-326f5c455c3c@iee.email","subject":"Re: [PATCH v2 9/9] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-19T19:20:11Z","receivedAt":"2019-10-19T19:20:25Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"Hi Philip,\n\nOn Sat, Oct 19, 2019 at 5:30 PM Philip Oakley wrote:\n\n> On 19/10/2019 11:35, Christian Couder wrote:\n\n> > +static void write_reused_pack_one(size_t pos, struct hashfile *out,\n> > + struct pack_window **w_curs)\n> > +{\n> > + off_t offset, next, cur;\n> > + enum object_type type;\n> > + unsigned long size;\n>\n> Is this a mem_sized size or a counter for less that 4GiB items?\n\nWhat I can see is that `&size` is passed as the last argument to\nunpack_object_header() below. And unpack_object_header() is defined in\npackfile.h like this:\n\nint unpack_object_header(struct packed_git *, struct pack_window **,\noff_t *, unsigned long *);\n\nsince at least 336226c259 (packfile.h: drop extern from function\ndeclarations, 2019-04-05)\n\nSo fixing this, if it needs to be fixed, should probably be part of a\nseparate topic fixing unpack_object_header().\n\n> > +\n> > + offset = reuse_packfile->revindex[pos].offset;\n> > + next = reuse_packfile->revindex[pos + 1].offset;\n> >\n> > - if (reuse_packfile_offset < 0)\n> > - reuse_packfile_offset = reuse_packfile->pack_size - the_hash_algo->rawsz;\n> > + record_reused_object(offset, offset - hashfile_total(out));\n> >\n> > - total = to_write = reuse_packfile_offset - sizeof(struct pack_header);\n> > + cur = offset;\n> > + type = unpack_object_header(reuse_packfile, w_curs, &cur, &size);\n> > + assert(type >= 0);\n\n> > +static void try_partial_reuse(struct bitmap_index *bitmap_git,\n> > + size_t pos,\n> > + struct bitmap *reuse,\n> > + struct pack_window **w_curs)\n> > {\n> > + struct revindex_entry *revidx;\n> > + off_t offset;\n> > + enum object_type type;\n> > + unsigned long size;\n>\n> Is this mem_sized or a <4GiB size?\n\nAgain this `size` variable is passed as the last argument to\nunpack_object_header() below.\n\n...\n\n> Apologies if these are dumb queries..\n\nI think it's a valid concern, so it's certainly ok for you to ask\nthese questions.\n"},{"id":"384458","messageId":"c1764a23-15d1-cbef-a675-0f4242bc41f4@iee.email","threadId":"52072","inReplyTo":"CAP8UFD2dLPguCnUhTu+F4SNPxFZ7YT5io0qXkVwvSNP-sA8Jxg@mail.gmail.com","subject":"Re: [PATCH v2 5/9] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2019-10-19T20:15:23Z","receivedAt":"2019-10-19T20:15:29Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Hi Christian,\n\nOn 19/10/2019 19:55, Christian Couder wrote:\n> Hi Philip,\n>\n> On Sat, Oct 19, 2019 at 5:25 PM Philip Oakley wrote:\n>> Hi Christian,\n>> can I check one thing?\n> Yeah, sure! Thanks for taking a look at my patches!\n>\n>> On 19/10/2019 11:35, Christian Couder wrote:\n>>> +int bitmap_walk_contains(struct bitmap_index *bitmap_git,\n>>> + struct bitmap *bitmap, const struct object_id *oid)\n>>> +{\n>>> + int idx;\n>> Excuse my ignorance here...\n>>\n>> For the case on Windows (int/long 32 bit), is this return value\n>> guaranteed to be less than 2GiB, i.e. not a memory offset?\n>>\n>> I'm just thinking ahead to the resolution of the 4GiB file limit issue\n>> on Git-for-Windows (https://github.com/git-for-windows/git/pull/2179)\n> I understand your concern, unfortunately, below we have:\n>\n> idx = bitmap_position(bitmap_git, oid);\n>\n> and bitmap_position() returns an int at least since 3ae5fa0768\n> (pack-bitmap: remove bitmap_git global variable, 2018-06-07)\n>\n> So I think the fix would be much more involved than just changing the\n> type of the idx variable. It would likely involve modifying\n> bitmap_position(), and thus would probably best be addressed in a\n> separate patch series.\n\nSo, IIUC it is mem-sized, so I should at least note it and pay attention \nto it for my >4G series, which like you say is \"much more involved than \njust\"...\n\nThe patch to flip over all the affected locations is a bit humongous \n(big), plus it's a bit of a moving target...\n>>> +\n>>> + if (!bitmap)\n>>> + return 0;\n>>> +\n>>> + idx = bitmap_position(bitmap_git, oid);\n>>> + return idx >= 0 && bitmap_get(bitmap, idx);\n>>> +}\nPhilip\n"},{"id":"384460","messageId":"20191019231836.GA32408@sigill.intra.peff.net","threadId":"52072","inReplyTo":"dce8e0b5-c4ea-f4f6-6275-1322f2d7200b@iee.email","subject":"Re: [PATCH v2 5/9] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-19T23:18:36Z","receivedAt":"2019-10-19T23:18:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Oct 19, 2019 at 04:25:19PM +0100, Philip Oakley wrote:\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> Excuse my ignorance here...\n> \n> For the case on Windows (int/long 32 bit), is this return value guaranteed\n> to be less than 2GiB, i.e. not a memory offset?\n> \n> I'm just thinking ahead to the resolution of the 4GiB file limit issue on\n> Git-for-Windows (https://github.com/git-for-windows/git/pull/2179)\n\nYes, it's not a memory offset.\n\nThis \"idx\" here (and the return value of bitmap_position) represents a\nposition within an array of objects. This isn't strictly limited to the\nobjects in a single pack (because a traversal might extend to objects\noutside the bitmapped pack), but we can use that as a general ballpark.\nAnd it's limited to a 4-byte object count already.\n\nSo the \"best\" type here would be a uint32_t (which is used elsewhere\nin the pack code), but we use signedness to indicate that the object\nwasn't found.\n\nThat's probably OK. The biggest repos I've seen have on the order of\n10-100M objects. That still gives us a factor of 20 before we hit 2^31.\nIf we imagine those repos took 10 years or so to accrue that many\nobjects, then we probably still have 200 years of growth left. Of course\ngrowth accelerates over time, but I suspect repos with 2B objects will\nrun into other scaling problems first. So I don't think it's worth\nworrying about too much for now.\n\n-Peff\n"},{"id":"384461","messageId":"20191019232322.GB32408@sigill.intra.peff.net","threadId":"52072","inReplyTo":"CAP8UFD2rsZj3=KoPCEWw2sTXFhNkynrJLeAGWK2vEbD5GU8chA@mail.gmail.com","subject":"Re: [PATCH v2 9/9] pack-objects: improve partial packfile reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-19T23:23:23Z","receivedAt":"2019-10-19T23:23:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Oct 19, 2019 at 09:20:11PM +0200, Christian Couder wrote:\n\n> > > +static void write_reused_pack_one(size_t pos, struct hashfile *out,\n> > > + struct pack_window **w_curs)\n> > > +{\n> > > + off_t offset, next, cur;\n> > > + enum object_type type;\n> > > + unsigned long size;\n> >\n> > Is this a mem_sized size or a counter for less that 4GiB items?\n> \n> What I can see is that `&size` is passed as the last argument to\n> unpack_object_header() below. And unpack_object_header() is defined in\n> packfile.h like this:\n> \n> int unpack_object_header(struct packed_git *, struct pack_window **,\n> off_t *, unsigned long *);\n> \n> since at least 336226c259 (packfile.h: drop extern from function\n> declarations, 2019-04-05)\n> \n> So fixing this, if it needs to be fixed, should probably be part of a\n> separate topic fixing unpack_object_header().\n\nYeah, this one definitely should be moved to whatever we used to\nrepresent object sizes in the future (size_t, or I guess off_t if we\nreally want to handle huge objects on 32-bit systems too). But\ndefinitely it shouldn't happen in this series, and I don't think anybody\ninterested in the other topic (converting the integer type for object\nsizes) needs to keep tabs on it. When they convert\nunpack_object_header(), the compiler will complain because of passing\nit as a pointer (the more insidious ones will be where we return an\nunsigned long to represent an object type, and somebody will have to\nlook into every caller).\n\n-Peff\n"},{"id":"384474","messageId":"ac89d8ed-5a57-6297-5fc2-cf562c8da812@iee.email","threadId":"52072","inReplyTo":"20191019232322.GB32408@sigill.intra.peff.net","subject":"Re: [PATCH v2 9/9] pack-objects: improve partial packfile reuse","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2019-10-20T11:26:01Z","receivedAt":"2019-10-20T11:26:08Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"On 20/10/2019 00:23, Jeff King wrote:\n> On Sat, Oct 19, 2019 at 09:20:11PM +0200, Christian Couder wrote:\n>\n>>>> +static void write_reused_pack_one(size_t pos, struct hashfile *out,\n>>>> + struct pack_window **w_curs)\n>>>> +{\n>>>> + off_t offset, next, cur;\n>>>> + enum object_type type;\n>>>> + unsigned long size;\n>>> Is this a mem_sized size or a counter for less that 4GiB items?\n>> What I can see is that `&size` is passed as the last argument to\n>> unpack_object_header() below. And unpack_object_header() is defined in\n>> packfile.h like this:\n>>\n>> int unpack_object_header(struct packed_git *, struct pack_window **,\n>> off_t *, unsigned long *);\n>>\n>> since at least 336226c259 (packfile.h: drop extern from function\n>> declarations, 2019-04-05)\n>>\n>> So fixing this, if it needs to be fixed, should probably be part of a\n>> separate topic fixing unpack_object_header().\n> Yeah, this one definitely should be moved to whatever we used to\n> represent object sizes in the future (size_t, or I guess off_t if we\n> really want to handle huge objects on 32-bit systems too). But\n> definitely it shouldn't happen in this series, and I don't think anybody\n> interested in the other topic (converting the integer type for object\n> sizes) needs to keep tabs on it. When they convert\n> unpack_object_header(), the compiler will complain because of passing\n> it as a pointer (the more insidious ones will be where we return an\n> unsigned long to represent an object type, and somebody will have to\n> look into every caller).\n>\nThanks, I'll add that one to my list of size values that I should check \nwhen rebasing my current series.\n\nIf I understand correctly gcc is no longer detecting those size \nconversions, but clang has -Wshorten-64-to-32 but I've still to check if \nit catches some of these conversion issues (esp when int (32) is \nextended to 64 bit size_t, rather than being 64 bit in the first place)\n\nPhilip\n"},{"id":"384615","messageId":"20191022174628.115505-1-jonathantanmy@google.com","threadId":"52072","inReplyTo":"20191019103531.23274-4-chriscool@tuxfamily.org","subject":"Re: [PATCH v2 3/9] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-22T17:46:28Z","receivedAt":"2019-10-22T17:46:40Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> From: Jeff King \n> \n> In a following commit we will need to allocate a variable\n> number of bitmap words, instead of always 32, so let's add\n> bitmap_word_alloc() for this purpose.\n> \n> We will also always access at least one word for each bitmap,\n> so we want to make sure that at least one is always\n> allocated.\n\nThe last paragraph is not true - we still can allocate 0. (We just ensure\nthat when we grow, we grow to at least 1.) I think we should just\ndelete the last paragraph - the first paragraph is sufficient.\n\nOther than that, all patches up to but not including the last one look\ngood, except the ones that just add a new function because I'll have to\nreview the last patch to see how they are used.\n"},{"id":"384623","messageId":"20191022194805.139215-1-jonathantanmy@google.com","threadId":"52072","inReplyTo":"20191019103531.23274-10-chriscool@tuxfamily.org","subject":"Re: [PATCH v2 9/9] pack-objects: improve partial packfile reuse","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-22T19:48:05Z","receivedAt":"2019-10-22T19:48:14Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"First, the commit message could probably be reordered to start with the\nmain point (reusing of packfiles at object granularity instead of\nallowing reuse of only one contiguous region). To specific points:\n\n> The dynamic array of `struct reused_chunk` is useful\n> because we need to know not just the number of zero bits,\n> but the accumulated offset due to missing objects.\n\nThe number of zero bits is irrelevant, I think. (I know I introduced\nthis idea, but at that time I was somehow confused that the offset was a\nnumber of objects and not a number of bytes.)\n\n> If a client both asks for a tag by sha1 and specifies\n> \"include-tag\", we may end up including the tag in the reuse\n> bitmap (due to the first thing), and then later adding it to\n> the packlist (due to the second). This results in duplicate\n> objects in the pack, which git chokes on. We should notice\n> that we are already including it when doing the include-tag\n> portion, and avoid adding it to the packlist.\n\nI still don't understand this part. Going off what's written in the\ncommit message here, it seems to me that the issue is that (1) an object\ncan be added to the reuse bitmap without going through to_pack, and (2)\nthis is done when the client asks for a tag by SHA-1. But all objects\nwhen specified by SHA-1 go through to_pack, don't they?\n\nOn to the review of the code. The ordering of - and + lines are\nconfusing, so I have just removed all - lines.\n\n> +/*\n> + * Record the offsets needed in our reused packfile chunks due to\n> + * \"gaps\" where we omitted some objects.\n> + */\n> +static struct reused_chunk {\n> +\toff_t start;\n> +\toff_t offset;\n> +} *reused_chunks;\n> +static int reused_chunks_nr;\n> +static int reused_chunks_alloc;\n\nA chunk is a set of objects from the original packfile that we are\nreusing; all objects in a chunk have the same relative position in the\noriginal packfile and the generated packfile. (This does not mean that\nthe bytes are exactly the same or, even, that the last object in the\nchunk has the same size in the original packfile and the generated\npackfile.)\n\n\"start\" is the offset of the first object of the chunk in the original\npackfile.\n\n\"offset\" is \"start\" minus the offset of the first object of the chunk in\nthe generated packfile. (I think it is easier to understand if this was\n\"new minus old\" instead of \"old minus new\", that is, the negation of its\ncurrent value.)\n\nSo I would prefer:\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 struct reused_chunk {\n /* The offset of the first object of this chunk in the original\n * packfile. */\n off_t original;\n /* The offset of the first object of this chunk in the generated\n * packfile minus \"original\". */\n off_t difference;\n }\n\n> +static void record_reused_object(off_t where, off_t offset)\n\nStraightforward, other than the renaming of parameters.\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\nAlso straightforward.\n\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> +\toffset = reuse_packfile->revindex[pos].offset;\n> +\tnext = reuse_packfile->revindex[pos + 1].offset;\n> \n> +\trecord_reused_object(offset, offset - hashfile_total(out));\n\nThis is where I understood what \"offset\" meant in struct reused_chunk.\n\n> \n> +\tcur = offset;\n> +\ttype = unpack_object_header(reuse_packfile, w_curs, &cur, &size);\n> +\tassert(type >= 0);\n> \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\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\nThe \"offset\" in \"reused offset\" is actually the difference in offset\nbetween the original packfile and the generated packfile, as I explained\nearlier. If the base_original->base_generated and\ndelta_original->delta_generated distances are the same, then nothing\nneeds to be done, as the comment above correctly explains.\n\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\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\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\nWe can write verbatim if (OFS + allow_ofs_delta + no fixup necessary) or\nif it is REF.\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\trecord_reused_object(sizeof(struct pack_header), 0);\n\nProbably worth a comment, since we're recording one chunk, not one\nobject. The code is correct, though - one big chunk with original offset\nas written, and no difference between original and generated offsets.\n\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\tdisplay_progress(progress_state, written);\n> \t}\n> +\treturn pos;\n> +}\n\nThe number of objects written is always a multiple of , but that's fine.\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> +\tunuse_pack(&w_curs);\n> }\n\nLooks straightforward to me. I found the inner \"for\" loop a bit\nconfusing, because the counter variable (\"offset\") is incremented both\nin the 3rd clause and in the body.\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\nStraightforward.\n\n> @@ -1001,6 +1119,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> @@ -2555,7 +2677,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> +\t\t(reuse_packfile_bitmap &&\n> +\t\t bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));\n> }\n\nThese are the parts I was confused about, as I said when I was\ndiscussing the commit message.\n\n> @@ -2661,6 +2785,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\nUnnecessary added line - please remove.\n\nOn to pack-bitmap.c.\n\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\nIs this case possible? try_partial_reuse() is only called when there is\na 1 at the bit location.\n\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 * If we got here, then the object is OK to reuse. Mark it.\n> \t */\n> +\tbitmap_set(reuse, pos);\n> +}\n\nOK. Thanks for the great comments.\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> +\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> +\twhile (i < result->word_alloc && result->words[i] == (eword_t)~0)\n> +\t\ti++;\n\nSkip through fully-1 words so that we don't have to iterate through\nevery bit - sounds good.\n\n> \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\nWhy is this necessary? Let's say we have 42 fully-1 words, and therefore\ni is 42. Shouldn't we allocate 42 words in our reuse bitmap?\n\n> \n> +\treuse = bitmap_word_alloc(i);\n> +\tmemset(reuse->words, 0xFF, i * sizeof(eword_t));\n> \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> +\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\ttry_partial_reuse(bitmap_git, pos + offset, reuse, &w_curs);\n> +\t\t}\n> \t}\n> \n> +\tunuse_pack(&w_curs);\n> \n> +\t*entries = bitmap_popcount(reuse);\n> +\tif (!*entries) {\n> +\t\tbitmap_free(reuse);\n> \t\treturn -1;\n> +\t}\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\nLooks good.\n\nAnd thanks for this patch - other than the difficult-to-understand parts\nI described above, I found the overall flow easy to discern.\n\nI presume tests would also need to be written. One way is to introduce\nyet another test variable, but maybe that is overkill.\n"},{"id":"384908","messageId":"CAP8UFD0PfCb+NfPDZ36c9MLcOa2xN9C9viOEEaLrbeA8Y9Rd7A@mail.gmail.com","threadId":"52072","inReplyTo":"20191022194805.139215-1-jonathantanmy@google.com","subject":"Re: [PATCH v2 9/9] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-26T09:29:17Z","receivedAt":"2019-10-26T09:29:52Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Oct 22, 2019 at 9:48 PM Jonathan Tan wrote:\n>\n> First, the commit message could probably be reordered to start with the\n> main point (reusing of packfiles at object granularity instead of\n> allowing reuse of only one contiguous region). To specific points:\n\nDone in my current version.\n\n> > The dynamic array of `struct reused_chunk` is useful\n> > because we need to know not just the number of zero bits,\n> > but the accumulated offset due to missing objects.\n>\n> The number of zero bits is irrelevant, I think. (I know I introduced\n> this idea, but at that time I was somehow confused that the offset was a\n> number of objects and not a number of bytes.)\n\nOk, I removed \"not just the number of zero bits,\".\n\n> > If a client both asks for a tag by sha1 and specifies\n> > \"include-tag\", we may end up including the tag in the reuse\n> > bitmap (due to the first thing), and then later adding it to\n> > the packlist (due to the second). This results in duplicate\n> > objects in the pack, which git chokes on. We should notice\n> > that we are already including it when doing the include-tag\n> > portion, and avoid adding it to the packlist.\n>\n> I still don't understand this part. Going off what's written in the\n> commit message here, it seems to me that the issue is that (1) an object\n> can be added to the reuse bitmap without going through to_pack, and (2)\n> this is done when the client asks for a tag by SHA-1. But all objects\n> when specified by SHA-1 go through to_pack, don't they?\n\nThat's how Peff explained it in response to one of your previous\nmessages. Peff, would you mind answering Jonathan's questions?\n\nAt the end of the commit message I added the following which might help though:\n\n>> No tests, because git does not actually exhibit this \"ask\n>> for it and also include-tag\" behavior. We do one or the\n>> other on clone, depending on whether --single-branch is set.\n>> However, libgit2 does both.\n\nSo my wild guess sould be that maybe the reason is that some of this\ncode was shared (or intended to be shared) with libgit2?\n\n> On to the review of the code. The ordering of - and + lines are\n> confusing, so I have just removed all - lines.\n>\n> > +/*\n> > + * Record the offsets needed in our reused packfile chunks due to\n> > + * \"gaps\" where we omitted some objects.\n> > + */\n> > +static struct reused_chunk {\n> > + off_t start;\n> > + off_t offset;\n> > +} *reused_chunks;\n> > +static int reused_chunks_nr;\n> > +static int reused_chunks_alloc;\n>\n> A chunk is a set of objects from the original packfile that we are\n> reusing; all objects in a chunk have the same relative position in the\n> original packfile and the generated packfile. (This does not mean that\n> the bytes are exactly the same or, even, that the last object in the\n> chunk has the same size in the original packfile and the generated\n> packfile.)\n>\n> \"start\" is the offset of the first object of the chunk in the original\n> packfile.\n>\n> \"offset\" is \"start\" minus the offset of the first object of the chunk in\n> the generated packfile. (I think it is easier to understand if this was\n> \"new minus old\" instead of \"old minus new\", that is, the negation of its\n> current value.)\n>\n> So I would prefer:\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> struct reused_chunk {\n> /* The offset of the first object of this chunk in the original\n> * packfile. */\n> off_t original;\n> /* The offset of the first object of this chunk in the generated\n> * packfile minus \"original\". */\n> off_t difference;\n> }\n\nOk, I have used that though it introduces some discrepancies, as\nrecord_reused_object() for example still has an \"offset\" argument.\n\n> > +static size_t write_reused_pack_verbatim(struct hashfile *out,\n> > + struct pack_window **w_curs)\n> > +{\n> > + size_t pos = 0;\n> > +\n> > + while (pos < reuse_packfile_bitmap->word_alloc &&\n> > + reuse_packfile_bitmap->words[pos] == (eword_t)~0)\n> > + pos++;\n> > +\n> > + if (pos) {\n> > + off_t to_write;\n> > +\n> > + written = (pos * BITS_IN_EWORD);\n> > + to_write = reuse_packfile->revindex[written].offset\n> > + - sizeof(struct pack_header);\n> > +\n> > + record_reused_object(sizeof(struct pack_header), 0);\n>\n> Probably worth a comment, since we're recording one chunk, not one\n> object.\n\nOk, added a comment.\n\n> The code is correct, though - one big chunk with original offset\n> as written, and no difference between original and generated offsets.\n\n\n> > @@ -2661,6 +2785,7 @@ static void prepare_pack(int window, int depth)\n> >\n> > if (nr_deltas && n > 1) {\n> > unsigned nr_done = 0;\n> > +\n> > if (progress)\n> > progress_state = start_progress(_(\"Compressing objects\"),\n> > nr_deltas);\n>\n> Unnecessary added line - please remove.\n\nWe often separate variable declaration from the rest of function code\nwith a blank line, so I don't think the added line is completely\nunnecessary. It helps make the code more standard and therefore more\nreadable, so I left it.\n\nYou might say that it should be in a preparatory patch, but a\npreparatory patch for just such a small change is a bit wasteful. I\nthink it's ok to add this blank line \"while at it\" in this patch.\n\n> On to pack-bitmap.c.\n>\n> > +static void try_partial_reuse(struct bitmap_index *bitmap_git,\n> > + size_t pos,\n> > + struct bitmap *reuse,\n> > + struct pack_window **w_curs)\n> > {\n> > + struct revindex_entry *revidx;\n> > + off_t offset;\n> > + enum object_type type;\n> > + unsigned long size;\n> > +\n> > + if (pos >= bitmap_git->pack->num_objects)\n> > + return; /* not actually in the pack */\n>\n> Is this case possible? try_partial_reuse() is only called when there is\n> a 1 at the bit location.\n\nI'd like Peff to answer here too, as I don't think I fully understand\nwhat's going on here.\n\n> > + /* Don't mark objects not in the packfile */\n> > + if (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)\n> > + i = bitmap_git->pack->num_objects / BITS_IN_EWORD;\n>\n> Why is this necessary? Let's say we have 42 fully-1 words, and therefore\n> i is 42. Shouldn't we allocate 42 words in our reuse bitmap?\n\nI'd also prefer Peff to answer here.\n\n[...]\n\n> And thanks for this patch - other than the difficult-to-understand parts\n> I described above, I found the overall flow easy to discern.\n>\n> I presume tests would also need to be written. One way is to introduce\n> yet another test variable, but maybe that is overkill.\n\nThis part of the commit message might again help understand why there\nis no test:\n\n>> No tests, because git does not actually exhibit this \"ask\n>> for it and also include-tag\" behavior. We do one or the\n>> other on clone, depending on whether --single-branch is set.\n>> However, libgit2 does both.\n\nBut I'd be again happy if Peff could confirm.\n\nThanks for another review,\nChristian.\n"},{"id":"384909","messageId":"CAP8UFD05uH7m7p0iR6g91MEd1QFd8vrJpKeKXsi0Brb9PKVQMg@mail.gmail.com","threadId":"52072","inReplyTo":"20191022174628.115505-1-jonathantanmy@google.com","subject":"Re: [PATCH v2 3/9] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-26T09:29:42Z","receivedAt":"2019-10-26T09:34:32Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Tue, Oct 22, 2019 at 7:46 PM Jonathan Tan wrote:\n>\n> > From: Jeff King \n> >\n> > In a following commit we will need to allocate a variable\n> > number of bitmap words, instead of always 32, so let's add\n> > bitmap_word_alloc() for this purpose.\n> >\n> > We will also always access at least one word for each bitmap,\n> > so we want to make sure that at least one is always\n> > allocated.\n>\n> The last paragraph is not true - we still can allocate 0. (We just ensure\n> that when we grow, we grow to at least 1.) I think we should just\n> delete the last paragraph - the first paragraph is sufficient.\n\nOk, I removed the last paragraph in my current version.\n\n> Other than that, all patches up to but not including the last one look\n> good, except the ones that just add a new function because I'll have to\n> review the last patch to see how they are used.\n\nThanks for your review,\nChristian.\n"}]}