{"thread":{"id":"51843","subject":"[RFC PATCH 00/10] Rewrite packfile reuse code","startedAt":"2019-09-13T13:02:52Z","lastAt":"2019-10-17T07:25:10Z","messageCount":31,"participants":["Christian Couder","Junio C Hamano","Jeff King","Jonathan Tan"],"isPatch":true,"patchVersion":1,"patchTotal":10},"messages":[{"id":"382291","messageId":"20190913130226.7449-1-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":null,"subject":"[RFC PATCH 00/10] Rewrite packfile reuse code","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:16Z","receivedAt":"2019-09-13T13:02:52Z","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\nThis is an RFC patch series that mostly for now just tries to split\nthe code into separate commits. If this split is considered ok, then\ncommit messages will be improved and some doc will be added\n(especially doc for pack.allowPackReuse). Perhaps performance test\nresults will also be provided.\n\nMost of the changes are in the last patch (10/10) and I haven't found\na good way to split them into several patches. Ideas are welcome. In\neach of the other preparatory patches there is a small change that\nmight make sense separately.\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\nI have put Peff as the author of all the commits.\n\nJeff King (10):\n builtin/pack-objects: report reused packfile objects\n packfile: expose get_delta_base()\n ewah/bitmap: introduce bitmap_word_alloc()\n ewah/bitmap: always allocate 2 more words\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 builtin/pack-objects.c | 248 +++++++++++++++++++++++++++++++++--------\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 8 files changed, 358 insertions(+), 110 deletions(-)\n\n-- \n2.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382292","messageId":"20190913130226.7449-2-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 01/10] builtin/pack-objects: report reused packfile objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:17Z","receivedAt":"2019-09-13T13:02:53Z","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 76ce906946..c11b2ea8d4 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -3525,7 +3525,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.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382293","messageId":"20190913130226.7449-3-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 02/10] packfile: expose get_delta_base()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:18Z","receivedAt":"2019-09-13T13:02:53Z","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 fc43a6c52c..5a6e8d54f1 100644\n--- a/packfile.c\n+++ b/packfile.c\n@@ -1191,11 +1191,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 3e98910bdd..8049202f4c 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.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382295","messageId":"20190913130226.7449-7-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 06/10] pack-bitmap: introduce bitmap_walk_contains()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:22Z","receivedAt":"2019-09-13T13:02:56Z","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 patch 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 b2422fed8f..1833971dc7 100644\n--- a/pack-bitmap.c\n+++ b/pack-bitmap.c\n@@ -828,6 +828,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 00de3ec8e4..5425767f0f 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.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382294","messageId":"20190913130226.7449-5-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 04/10] ewah/bitmap: always allocate 2 more words","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:20Z","receivedAt":"2019-09-13T13:02:57Z","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 patch we will allocate a variable number\nof words in some bitmaps. When iterating over the words we\nwill need a mark to tell us when to stop iterating. Let's\nalways allocate 2 more words, that will always contain 0,\nas that mark.\n\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n ewah/bitmap.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 143dc71419..eac05485f1 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -41,7 +41,7 @@ void bitmap_set(struct bitmap *self, size_t 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 + 1) * 2;\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));\n-- \n2.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382296","messageId":"20190913130226.7449-8-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 07/10] csum-file: introduce hashfile_total()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:23Z","receivedAt":"2019-09-13T13:02: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 need this helper function in a following patch\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.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382297","messageId":"20190913130226.7449-9-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 08/10] pack-objects: introduce pack.allowPackReuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:24Z","receivedAt":"2019-09-13T13:02:58Z","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 builtin/pack-objects.c | 8 +++++++-\n 1 file changed, 7 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex c11b2ea8d4..1664969c97 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@@ -2719,6 +2720,10 @@ static int git_pack_config(const char *k, const char *v, void *cb)\n \t\tsparse = 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@@ -3063,7 +3068,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n \tif (!(bitmap_git = prepare_bitmap_walk(revs)))\n \t\treturn -1;\n \n-\tif (pack_options_allow_reuse() &&\n+\tif (allow_pack_reuse &&\n+\t pack_options_allow_reuse() &&\n \t !reuse_partial_packfile_from_bitmap(\n \t\t\tbitmap_git,\n \t\t\t&reuse_packfile,\n-- \n2.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382299","messageId":"20190913130226.7449-4-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 03/10] ewah/bitmap: introduce bitmap_word_alloc()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:19Z","receivedAt":"2019-09-13T13:02:59Z","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 patch 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\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n ewah/bitmap.c | 11 ++++++++---\n ewah/ewok.h | 1 +\n 2 files changed, 9 insertions(+), 3 deletions(-)\n\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 52f1178db4..143dc71419 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -22,14 +22,19 @@\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);\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.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382298","messageId":"20190913130226.7449-6-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 05/10] pack-bitmap: don't rely on bitmap_git->reuse_objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:21Z","receivedAt":"2019-09-13T13:03:00Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"From: Jeff King \n\nAs we now allocate 2 more words than necessary for each\nbitmap to serve as marks telling us that we can stop\niterating over the words, we don't need to rely on\nbitmap_git->reuse_objects to stop iterating over the words.\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 ed2befaac6..b2422fed8f 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.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382300","messageId":"20190913130226.7449-11-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:26Z","receivedAt":"2019-09-13T13:03:00Z","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\nSigned-off-by: Jeff King \nSigned-off-by: Christian Couder \n---\n builtin/pack-objects.c | 227 +++++++++++++++++++++++++++++++++--------\n pack-bitmap.c | 150 +++++++++++++++++++--------\n pack-bitmap.h | 3 +-\n 3 files changed, 293 insertions(+), 87 deletions(-)\n\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 5ee0b3092d..6822ac1026 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,189 @@ 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-\tif (reuse_packfile_offset < 0)\n-\t\treuse_packfile_offset = reuse_packfile->pack_size - the_hash_algo->rawsz;\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-\ttotal = to_write = reuse_packfile_offset - sizeof(struct pack_header);\n+\toffset = reuse_packfile->revindex[pos].offset;\n+\tnext = reuse_packfile->revindex[pos + 1].offset;\n \n-\twhile (to_write) {\n-\t\tint read_pack = xread(fd, buffer, sizeof(buffer));\n+\trecord_reused_object(offset, offset - hashfile_total(out));\n \n-\t\tif (read_pack <= 0)\n-\t\t\tdie_errno(_(\"unable to read from reused packfile\"));\n+\tcur = offset;\n+\ttype = unpack_object_header(reuse_packfile, w_curs, &cur, &size);\n+\tassert(type >= 0);\n \n-\t\tif (read_pack > to_write)\n-\t\t\tread_pack = to_write;\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\thashwrite(f, buffer, read_pack);\n-\t\tto_write -= read_pack;\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\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\tif (0) {\n+\t\t\t\toff_t expected_size = cur - offset;\n+\n+\t\t\t\tif (len + ofs_len < expected_size) {\n+\t\t\t\t\tunsigned max_pad = (len >= 4) ? 9 : 5;\n+\t\t\t\t\theader[len - 1] |= 0x80;\n+\t\t\t\t\twhile (len < max_pad && len + ofs_len < expected_size)\n+\t\t\t\t\t\theader[len++] = 0x80;\n+\t\t\t\t\theader[len - 1] &= 0x7F;\n+\t\t\t\t}\n+\t\t\t}\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 +1000,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@@ -1002,6 +1132,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, index_pos);\n \tif (!entry)\n \t\treturn 0;\n@@ -1192,6 +1326,7 @@ static int add_object_entry(const struct object_id *oid, enum object_type type,\n \tcreate_object_entry(oid, type, pack_name_hash(name),\n \t\t\t exclude, name && no_try_delta(name),\n \t\t\t index_pos, found_pack, found_offset);\n+\n \treturn 1;\n }\n \n@@ -2571,7 +2706,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, NULL);\n+\treturn packlist_find(&to_pack, oid, NULL) ||\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@@ -2677,6 +2814,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@@ -3061,7 +3199,6 @@ static void loosen_unused_packed_objects(void)\n static int pack_options_allow_reuse(void)\n {\n \treturn 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@@ -3079,7 +3216,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 1833971dc7..1d4c95ebc1 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@@ -766,65 +773,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 5425767f0f..7af7335f2e 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 **bitmap);\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.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382301","messageId":"20190913130226.7449-10-chriscool@tuxfamily.org","threadId":"51843","inReplyTo":"20190913130226.7449-1-chriscool@tuxfamily.org","subject":"[RFC PATCH 09/10] builtin/pack-objects: introduce obj_is_packed()","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-09-13T13:02:25Z","receivedAt":"2019-09-13T13:03:00Z","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 1664969c97..5ee0b3092d 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -2569,6 +2569,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, NULL);\n+}\n+\n static void add_tag_chain(const struct object_id *oid)\n {\n \tstruct tag *tag;\n@@ -2580,7 +2585,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, NULL))\n+\tif (obj_is_packed(oid))\n \t\treturn;\n \n \ttag = lookup_tag(the_repository, oid);\n@@ -2604,7 +2609,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, NULL)) /* object packed? */\n+\t obj_is_packed(&peeled)) /* object packed? */\n \t\tadd_tag_chain(oid);\n \treturn 0;\n }\n-- \n2.23.0.46.gd213b4aca1.dirty\n\n"},{"id":"382341","messageId":"xmqqd0g3dgi5.fsf@gitster-ct.c.googlers.com","threadId":"51843","inReplyTo":"20190913130226.7449-9-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 08/10] pack-objects: introduce pack.allowPackReuse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-09-13T21:37:54Z","receivedAt":"2019-09-13T21:38:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> From: Jeff King \n>\n> Let's make it possible to configure if we want pack reuse or not.\n>\n> Signed-off-by: Jeff King \n> Signed-off-by: Christian Couder \n> ---\n> builtin/pack-objects.c | 8 +++++++-\n> 1 file changed, 7 insertions(+), 1 deletion(-)\n>\n> diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\n> index c11b2ea8d4..1664969c97 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> @@ -2719,6 +2720,10 @@ static int git_pack_config(const char *k, const char *v, void *cb)\n> \t\tsparse = 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> @@ -3063,7 +3068,8 @@ static int get_object_list_from_bitmap(struct rev_info *revs)\n> \tif (!(bitmap_git = prepare_bitmap_walk(revs)))\n> \t\treturn -1;\n> \n> -\tif (pack_options_allow_reuse() &&\n> +\tif (allow_pack_reuse &&\n> +\t pack_options_allow_reuse() &&\n\nIt somehow looks strange to have this code check for both\nallow_pack_reuse and pack_options_allow_reuse(). I would have\nexpected that the referene to the new variable to be contained in\nthe existing helper function, so that any future code that wants to\nask \"are we allowed to reuse?\" would get the same answer from the\nhelper consistently, without having to check the new variable.\n\n> \t !reuse_partial_packfile_from_bitmap(\n> \t\t\tbitmap_git,\n> \t\t\t&reuse_packfile,\n"},{"id":"382347","messageId":"xmqq7e6bde4z.fsf@gitster-ct.c.googlers.com","threadId":"51843","inReplyTo":"20190913130226.7449-11-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-09-13T22:29:00Z","receivedAt":"2019-09-13T22:29:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Christian Couder writes:\n\n> +/*\n> + * Record the offsets needed in our reused packfile chunks due to\n> + * \"gaps\" where we omitted some objects.\n> + */\n\nThe meaning of 'start' and 'offset' is unclear from the first\nreading. Is it \"starting offset\" and \"for how many bytes the region\nlasts\"? If so, 'offset', which is usually a location (unless you\nalways measure from the beginning, in which case you could say it\nnames the byte-size of a region), may be a misnomer (side note: I'll\npretend that I haven't realized the 'offset' may be the end offset\nof a region for now---this is a good illustration why a better\ncomment should be here anyway ;-).\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\nAnd here, 'start' is called 'where'; either is a good word for a\nlocation; we'd want to pick either one to be consistent, perhaps?\n\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\nThe reason why the above code works is because this function will\nalways be called in the ascending order of the 'offset'?\n\nHmmm, perhaps 'offset' is not a region-size after all. Is it the\nend offset, as opposed to 'start' which is the starting offset, and\nthe two offsets sandwitch a region?\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\nThis comment has nothing to do with the change, but the way the\npatch is presented is quite hard to follow, in that the preimage or\nthe common context lines do not help understand what the new code is\ndoing at all ;-)\n\nI'll come back to the remainder of the patch later. Thanks.\n"},{"id":"382355","messageId":"20190914020225.GB28422@sigill.intra.peff.net","threadId":"51843","inReplyTo":"xmqq7e6bde4z.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-09-14T02:02:25Z","receivedAt":"2019-09-14T02:02:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 13, 2019 at 03:29:00PM -0700, Junio C Hamano wrote:\n\n> This comment has nothing to do with the change, but the way the\n> patch is presented is quite hard to follow, in that the preimage or\n> the common context lines do not help understand what the new code is\n> doing at all ;-)\n> \n> I'll come back to the remainder of the patch later. Thanks.\n\nI applaud Christian's effort to tease it out into separate patches. I\nthink I may need to take a pass and try to explain what's going on in\nsome of them (which will definitely involve paging in some ancient work\nmentally, but hopefully between my memory and general familiarity with\nthe area, I can massage it into something a bit more understandable).\n\n-Peff\n"},{"id":"382356","messageId":"xmqqy2yrbmqu.fsf@gitster-ct.c.googlers.com","threadId":"51843","inReplyTo":"20190914020225.GB28422@sigill.intra.peff.net","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-09-14T03:06:01Z","receivedAt":"2019-09-14T03:09:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Fri, Sep 13, 2019 at 03:29:00PM -0700, Junio C Hamano wrote:\n>\n>> This comment has nothing to do with the change, but the way the\n>> patch is presented is quite hard to follow, in that the preimage or\n>> the common context lines do not help understand what the new code is\n>> doing at all ;-)\n>> \n>> I'll come back to the remainder of the patch later. Thanks.\n>\n> I applaud Christian's effort to tease it out into separate patches.\n\nAh, no question about it. I have a suspicion that 10/10 alone may\nstill be a bit too large a ball of wax, but with all the earlier\npreparatory steps are bite-sized and trivial to see how they are\ncorrect.\n\nThe \"way the patch is presented\" comment was not at all about what\nChristian did, but was about what the diff machinery computed when\ncomparing the 9th step Christian created and the final step. In its\nattempt to find and align common context lines, it ended up finding\nblank lines and almost nothing else in the earlier part of the\npatch, not just making it harder to read the new helper function\n(i.e. the best way to read record_reused_object(), for example, is\nto look only at '+' and ' ' lines, because the '-' lines are\nirrelevant), it also made it hard to see what got discarded.\n\n"},{"id":"383283","messageId":"20191002155721.GD6116@sigill.intra.peff.net","threadId":"51843","inReplyTo":"xmqqy2yrbmqu.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-02T15:57:22Z","receivedAt":"2019-10-02T15:57:24Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 13, 2019 at 08:06:01PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > On Fri, Sep 13, 2019 at 03:29:00PM -0700, Junio C Hamano wrote:\n> >\n> >> This comment has nothing to do with the change, but the way the\n> >> patch is presented is quite hard to follow, in that the preimage or\n> >> the common context lines do not help understand what the new code is\n> >> doing at all ;-)\n> >> \n> >> I'll come back to the remainder of the patch later. Thanks.\n> >\n> > I applaud Christian's effort to tease it out into separate patches.\n> \n> Ah, no question about it. I have a suspicion that 10/10 alone may\n> still be a bit too large a ball of wax, but with all the earlier\n> preparatory steps are bite-sized and trivial to see how they are\n> correct.\n> \n> The \"way the patch is presented\" comment was not at all about what\n> Christian did, but was about what the diff machinery computed when\n> comparing the 9th step Christian created and the final step. In its\n> attempt to find and align common context lines, it ended up finding\n> blank lines and almost nothing else in the earlier part of the\n> patch, not just making it harder to read the new helper function\n> (i.e. the best way to read record_reused_object(), for example, is\n> to look only at '+' and ' ' lines, because the '-' lines are\n> irrelevant), it also made it hard to see what got discarded.\n\nHmm, I see the early parts of this graduated to 'next'. I'm not sure\neverything there is completely correct, though. E.g. I'm not sure of the\nreasoning in df75281e78 (ewah/bitmap: always allocate 2 more words,\n2019-09-13).\n\nI think the \"block+1\" there is actually because \"block\" might be \"0\".\nPrior to 2820ed171a (ewah/bitmap: introduce bitmap_word_alloc(),\n2019-09-13) from the same series, that could never be the case because\nwe know that we always start with at least 32 allocated words. But after\nthat we _could_ start with an empty word array, and allocating \"block *\n2\" would not make forward progress.\n\nAnd then the \"2 more words\" thing is used as justification in the next\npatch, 04a32d357f (pack-bitmap: don't rely on bitmap_git->reuse_objects,\n2019-09-13). I won't say that there isn't some subtle dependency there,\nbut I certainly don't remember any logic like that at all. ;) So I think\nit might bear a little more scrutiny.\n\nI'm sorry for being so slow on giving it a more careful review. I was\ntraveling for work, then playing catch-up, and am now going on vacation.\nSo it might be a little while yet.\n\n-Peff\n"},{"id":"383322","messageId":"xmqq5zl6d1kv.fsf@gitster-ct.c.googlers.com","threadId":"51843","inReplyTo":"20191002155721.GD6116@sigill.intra.peff.net","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-10-03T02:06:56Z","receivedAt":"2019-10-03T02:07:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Hmm, I see the early parts of this graduated to 'next'. I'm not sure\n> everything there is completely correct, though. E.g. I'm not sure of the\n> reasoning in df75281e78 (ewah/bitmap: always allocate 2 more words,\n> 2019-09-13).\n> ...\n> I'm sorry for being so slow on giving it a more careful review. I was\n> traveling for work, then playing catch-up, and am now going on vacation.\n> So it might be a little while yet.\n\nThanks for a status update. I do not mind moving this topic much\nslower than other topics at all (if somebody is actively working on\nit, I do not even mind reverting the merge and requeuing an updated\nseries, but I do not think that is the case here). It would give me\nmuch more confidence in the topic if we can collectively promise\nourselves that we'll give it a good review before we let it graduate\nto 'master'.\n\nThanks.\n"},{"id":"383327","messageId":"CAP8UFD35BAhAJuxivUy=8+XmGXL4snRnsfHJXxgWO+jXfeMrxg@mail.gmail.com","threadId":"51843","inReplyTo":"xmqq5zl6d1kv.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-03T06:55:57Z","receivedAt":"2019-10-03T06:56:12Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Thu, Oct 3, 2019 at 4:06 AM Junio C Hamano wrote:\n>\n> Jeff King writes:\n>\n> > Hmm, I see the early parts of this graduated to 'next'. I'm not sure\n> > everything there is completely correct, though. E.g. I'm not sure of the\n> > reasoning in df75281e78 (ewah/bitmap: always allocate 2 more words,\n> > 2019-09-13).\n\nYeah, when I prepared the series I wondered why we allocate 2 more\nwords instead of just 1 more, but I forgot to ask that when sending\nit.\n\n> > I'm sorry for being so slow on giving it a more careful review. I was\n> > traveling for work, then playing catch-up, and am now going on vacation.\n> > So it might be a little while yet.\n>\n> Thanks for a status update. I do not mind moving this topic much\n> slower than other topics at all (if somebody is actively working on\n> it, I do not even mind reverting the merge and requeuing an updated\n> series, but I do not think that is the case here).\n\nI think the series requires at least documenting pack.allowPackReuse\nwhich is introduced in d35b73c5e9 (pack-objects: introduce\npack.allowPackReuse, 2019-09-13). I was planning to send an additional\npatch to do that, but if you prefer I can add the documentation to the\nsame commit that introduce the config variable and resend everything.\n\n> It would give me\n> much more confidence in the topic if we can collectively promise\n> ourselves that we'll give it a good review before we let it graduate\n> to 'master'.\n\nYeah, a review from Peff could be especially insightful as the code\ncomes from GitHub.\n"},{"id":"383850","messageId":"20191010234040.168894-1-jonathantanmy@google.com","threadId":"51843","inReplyTo":"20190913130226.7449-5-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 04/10] ewah/bitmap: always allocate 2 more words","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-10T23:40:40Z","receivedAt":"2019-10-10T23:40:46Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> From: Jeff King \n> \n> In a following patch we will allocate a variable number\n> of words in some bitmaps. When iterating over the words we\n> will need a mark to tell us when to stop iterating. Let's\n> always allocate 2 more words, that will always contain 0,\n> as that mark.\n\n[snip]\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 + 1) * 2;\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));\n\nThis patch set was mentioned as needing more thorough review in \"What's\nCooking\" [1], so I thought I'd give it a try. As Peff said [2], the\njustification in the commit message looks incorrect. He suggests that it\nis most likely because \"block\" might be 0 (which is possible because a\nprevious patch eliminated the minimum of 32), which makes sense to me.\n\nIn any case, the next patch does not use 0 as a sentinel mark. Iteration\nstops when word_alloc is reached anyway, and since this is a regular\nbitmap, 0 is a valid word and cannot be used as a sentinel. (Maybe 0 is\na valid word in a compressed EWAH bitmap too...not sure about that.)\n\nI think this should be squashed with patch 3, adding to that commit\nmessage \"since word_alloc might be 0, we need to change the growth\nfunction\". (Or just make the minimum word_alloc be 1 or 32 or something\npositive, if that's possible.)\n\n[1] https://public-inbox.org/git/xmqq36g5444k.fsf@gitster-ct.c.googlers.com/\n[2] https://public-inbox.org/git/20191002155721.GD6116@sigill.intra.peff.net/\n"},{"id":"383852","messageId":"20191010234408.170356-1-jonathantanmy@google.com","threadId":"51843","inReplyTo":"20190913130226.7449-6-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 05/10] pack-bitmap: don't rely on bitmap_git->reuse_objects","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-10T23:44:08Z","receivedAt":"2019-10-10T23:44:15Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> As we now allocate 2 more words than necessary for each\n> bitmap to serve as marks telling us that we can stop\n> iterating over the words, we don't need to rely on\n> bitmap_git->reuse_objects to stop iterating over the words.\n\nAs Peff states [1], this justification is probably incorrect as well.\nThe actual justification seems to be that we will no longer compute\nreuse_objects (in a future patch), so we cannot rely on it anymore to\nterminate the loop early; we have to iterate to the end.\n\n[1] https://public-inbox.org/git/20191002155721.GD6116@sigill.intra.peff.net/\n\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\nHere, iteration is not terminated when we see a 0. We just proceed to\nthe next one.\n"},{"id":"383853","messageId":"20191010235952.174426-1-jonathantanmy@google.com","threadId":"51843","inReplyTo":"20190913130226.7449-11-chriscool@tuxfamily.org","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-10T23:59:52Z","receivedAt":"2019-10-11T00:00:00Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"I'm going to start with pack-bitmap.h, then builtin/pack-objects.c.\n\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 **bitmap);\n\nMakes sense. The existing code determines if the given packfile is\nsuitable, and if yes, the span of the packfile to use. With this patch,\nwe resolve to use the given packfile, and want to compute which objects\nto use, storing the computation result in an uncompressed bitmap.\n(Resolving to use the given packfile is not that much different from\nexisting behavior, as far as I know, since we currently only consider\none packfile at most anyway.)\n\nSo replacing the out param makes sense, although a more descriptive name\nthan \"bitmap\" would be nice.\n\nSkipping pack-bitmaps.c for now.\n\nOK, builtin/pack-objects.c.\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\nThis makes sense - offsets may be different when we omit objects from\nthe packfile. I think this can be computed by calculating the number of\nzero bits between the current object's index and the nth object prior\n(where n is the offset) in the bitmap resulting from\nreuse_partial_packfile_from_bitmap() above, thus eliminating the need\nfor this array, but I haven't tested it.\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> \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> +\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\tif (0) {\n> +\t\t\t\toff_t expected_size = cur - offset;\n> +\n> +\t\t\t\tif (len + ofs_len < expected_size) {\n> +\t\t\t\t\tunsigned max_pad = (len >= 4) ? 9 : 5;\n> +\t\t\t\t\theader[len - 1] |= 0x80;\n> +\t\t\t\t\twhile (len < max_pad && len + ofs_len < expected_size)\n> +\t\t\t\t\t\theader[len++] = 0x80;\n> +\t\t\t\t\theader[len - 1] &= 0x7F;\n> +\t\t\t\t}\n> +\t\t\t}\n\nThis if(0) should be deleted.\n\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\nI didn't look into detail, but this looks like it's writing a single\nobject. In particular, it can convert OFS into REF, something that the\nexisting code cannot do.\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\tdisplay_progress(progress_state, written);\n> \t}\n> +\treturn pos;\n> +}\n\nI presume this optimization is needed for the case where we are using\n*all* objects of a packfile, as is typical during a clone.\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\nI didn't look into detail, but it looks like a straightforward loop.\n\n> @@ -1002,6 +1132,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\nHmm...why did we previously not need to check the reuse information, but\nwe do now? I gave the code a cursory glance but couldn't find the\nanswer.\n\n> @@ -2571,7 +2706,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, NULL);\n> +\treturn packlist_find(&to_pack, oid, NULL) ||\n> +\t\t(reuse_packfile_bitmap &&\n> +\t\t bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));\n\nSame question here - why do we need to check the reuse information?\n\n> @@ -3061,7 +3199,6 @@ static void loosen_unused_packed_objects(void)\n> static int pack_options_allow_reuse(void)\n> {\n> \treturn 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\nRelaxing of the allow_ofs_delta condition - makes sense given (as above)\nwe can convert OFS to REF.\n\nOverall I think that this makes sense, except for my unanswered\nquestions (and the presence of reused_chunk).\n"},{"id":"383880","messageId":"CAP8UFD0yefCapgLG78bqBY0ZNWNiifJZUxQ=MGDa8AVJJrWBFg@mail.gmail.com","threadId":"51843","inReplyTo":"20191010235952.174426-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-11T07:39:58Z","receivedAt":"2019-10-11T07:40:13Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Oct 11, 2019 at 1:59 AM Jonathan Tan wrote:\n>\n> I'm going to start with pack-bitmap.h, then builtin/pack-objects.c.\n>\n> > int reuse_partial_packfile_from_bitmap(struct bitmap_index *,\n> > struct packed_git **packfile,\n> > - uint32_t *entries, off_t *up_to);\n> > + uint32_t *entries,\n> > + struct bitmap **bitmap);\n>\n> Makes sense. The existing code determines if the given packfile is\n> suitable, and if yes, the span of the packfile to use. With this patch,\n> we resolve to use the given packfile, and want to compute which objects\n> to use, storing the computation result in an uncompressed bitmap.\n> (Resolving to use the given packfile is not that much different from\n> existing behavior, as far as I know, since we currently only consider\n> one packfile at most anyway.)\n>\n> So replacing the out param makes sense, although a more descriptive name\n> than \"bitmap\" would be nice.\n\nYeah, in pack-bitmap.c this argument is called \"reuse_out\", so the\nsame name could be used in pack-bitmap.c too. I changed that on my\ncurrent version.\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> This makes sense - offsets may be different when we omit objects from\n> the packfile. I think this can be computed by calculating the number of\n> zero bits between the current object's index and the nth object prior\n> (where n is the offset) in the bitmap resulting from\n> reuse_partial_packfile_from_bitmap() above, thus eliminating the need\n> for this array, but I haven't tested it.\n\nThanks for the idea. I will let others comment on that though before\nmaybe trying to implement it. I think it could come as a further\noptimization in a following patch if it makes things faster or reduce\nmemory usage.\n\n> > + if (0) {\n> > + off_t expected_size = cur - offset;\n> > +\n> > + if (len + ofs_len < expected_size) {\n> > + unsigned max_pad = (len >= 4) ? 9 : 5;\n> > + header[len - 1] |= 0x80;\n> > + while (len < max_pad && len + ofs_len < expected_size)\n> > + header[len++] = 0x80;\n> > + header[len - 1] &= 0x7F;\n> > + }\n> > + }\n>\n> This if(0) should be deleted.\n\nYeah, good eyes. I removed it on my current version.\n\n> > @@ -1002,6 +1132,10 @@ static int have_duplicate_entry(const struct object_id *oid,\n> > {\n> > struct object_entry *entry;\n> >\n> > + if (reuse_packfile_bitmap &&\n> > + bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid))\n> > + return 1;\n>\n> Hmm...why did we previously not need to check the reuse information, but\n> we do now? I gave the code a cursory glance but couldn't find the\n> answer.\n>\n> > @@ -2571,7 +2706,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> > - return !!packlist_find(&to_pack, oid, NULL);\n> > + return packlist_find(&to_pack, oid, NULL) ||\n> > + (reuse_packfile_bitmap &&\n> > + bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));\n>\n> Same question here - why do we need to check the reuse information?\n\nMaybe a reuse bitmap makes it cheap enough to check that information?\n\nThank you for the review,\nChristian.\n"},{"id":"383882","messageId":"CAP8UFD0-NHCj6KcbdMG3bCwWp=wUdoYugLggsbnpvr1d6-P4yg@mail.gmail.com","threadId":"51843","inReplyTo":"20191010234040.168894-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 04/10] ewah/bitmap: always allocate 2 more words","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-11T07:49:53Z","receivedAt":"2019-10-11T07:50:07Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Oct 11, 2019 at 1:40 AM Jonathan Tan wrote:\n>\n> > From: Jeff King \n> >\n> > In a following patch we will allocate a variable number\n> > of words in some bitmaps. When iterating over the words we\n> > will need a mark to tell us when to stop iterating. Let's\n> > always allocate 2 more words, that will always contain 0,\n> > as that mark.\n>\n> [snip]\n>\n> > if (block >= self->word_alloc) {\n> > size_t old_size = self->word_alloc;\n> > - self->word_alloc = block * 2;\n> > + self->word_alloc = (block + 1) * 2;\n> > REALLOC_ARRAY(self->words, self->word_alloc);\n> > memset(self->words + old_size, 0x0,\n> > (self->word_alloc - old_size) * sizeof(eword_t));\n>\n> This patch set was mentioned as needing more thorough review in \"What's\n> Cooking\" [1], so I thought I'd give it a try.\n\nThanks!\n\n> As Peff said [2], the\n> justification in the commit message looks incorrect. He suggests that it\n> is most likely because \"block\" might be 0 (which is possible because a\n> previous patch eliminated the minimum of 32), which makes sense to me.\n\nOk I will try to come up with a better justification, though Peff said\nthat he would took another look at this series and I'd rather wait\nuntil he has done that.\n\n> In any case, the next patch does not use 0 as a sentinel mark. Iteration\n> stops when word_alloc is reached anyway, and since this is a regular\n> bitmap, 0 is a valid word and cannot be used as a sentinel. (Maybe 0 is\n> a valid word in a compressed EWAH bitmap too...not sure about that.)\n\nYeah I misread this. Hopefully Peff can shed some light on this.\n\n> I think this should be squashed with patch 3, adding to that commit\n> message \"since word_alloc might be 0, we need to change the growth\n> function\". (Or just make the minimum word_alloc be 1 or 32 or something\n> positive, if that's possible.)\n\nYeah, thank you for the suggestion. I still wonder why 2 is added\ninstead of just 1 though.\n"},{"id":"383883","messageId":"CAP8UFD0mZgN5=Bva6drLoAusMTomTZ9X=jRCeGgrTBK-mxCBLw@mail.gmail.com","threadId":"51843","inReplyTo":"20191010234408.170356-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 05/10] pack-bitmap: don't rely on bitmap_git->reuse_objects","fromName":"Christian Couder","fromEmail":"christian.couder@gmail.com","sentAt":"2019-10-11T07:50:01Z","receivedAt":"2019-10-11T07:50:15Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"On Fri, Oct 11, 2019 at 1:44 AM Jonathan Tan wrote:\n>\n> > As we now allocate 2 more words than necessary for each\n> > bitmap to serve as marks telling us that we can stop\n> > iterating over the words, we don't need to rely on\n> > bitmap_git->reuse_objects to stop iterating over the words.\n>\n> As Peff states [1], this justification is probably incorrect as well.\n> The actual justification seems to be that we will no longer compute\n> reuse_objects (in a future patch), so we cannot rely on it anymore to\n> terminate the loop early; we have to iterate to the end.\n>\n> [1] https://public-inbox.org/git/20191002155721.GD6116@sigill.intra.peff.net/\n\nOk, thanks! I will change the description.\n"},{"id":"383912","messageId":"20191011180125.GA20601@sigill.intra.peff.net","threadId":"51843","inReplyTo":"20191010235952.174426-1-jonathantanmy@google.com","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-11T18:01:25Z","receivedAt":"2019-10-11T18:01:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 10, 2019 at 04:59:52PM -0700, Jonathan Tan wrote:\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> \n> This makes sense - offsets may be different when we omit objects from\n> the packfile. I think this can be computed by calculating the number of\n> zero bits between the current object's index and the nth object prior\n> (where n is the offset) in the bitmap resulting from\n> reuse_partial_packfile_from_bitmap() above, thus eliminating the need\n> for this array, but I haven't tested it.\n\nYou need to know not just the number of zero bits, but the accumulated\noffset due to those missing objects. So you'd end up having to walk over\nthe revindex for that set of objects. This array is basically caching\nthose accumulated offsets (for the parts we _do_ include) so we don't\nhave to compute them repeatedly.\n\nThere's also a more subtle issue with entry sizes; see below.\n\n> > +\t\t\tif (0) {\n> > +\t\t\t\toff_t expected_size = cur - offset;\n> > +\n> > +\t\t\t\tif (len + ofs_len < expected_size) {\n> > +\t\t\t\t\tunsigned max_pad = (len >= 4) ? 9 : 5;\n> > +\t\t\t\t\theader[len - 1] |= 0x80;\n> > +\t\t\t\t\twhile (len < max_pad && len + ofs_len < expected_size)\n> > +\t\t\t\t\t\theader[len++] = 0x80;\n> > +\t\t\t\t\theader[len - 1] &= 0x7F;\n> > +\t\t\t\t}\n> > +\t\t\t}\n> \n> This if(0) should be deleted.\n\nYeah, definitely. I had to scratch my head at what this code was doing.\nIIRC, the issue is this:\n\n - imagine we have a sequence of objects in a pack, A B C D, but we\n want to generate an output pack that contains just A C D\n\n - imagine C is a delta against A. We adjust its delta base offset to\n account for the absence of B\n\n - because the offset is stored in a variable-length encoding, that may mean\n that the entry for C gets shorter!\n\n - now imagine D is a delta against A, as well. We have to account for\n the missing B, but also for the shrunken C.\n\nThe current code does so by creating a new entry in the reused_chunks\narray. In the worst case that can grow to have the same number of\nentries as we have objects. So this code was an attempt to pad the\nheader of a shrunken entry to keep it the same size. I don't remember\nall the problems we ran into with that, but in the end we found that it\ndidn't actually help much, because in practice we don't end up with a\nlot of chunks anyway.\n\nFor instance, packing torvalds/linux on our servers just now reused 6.5M\nobjects, but only needed ~50k chunks.\n\n> > +\tcopy_pack_data(out, reuse_packfile, w_curs, offset, next - offset);\n> > +}\n> \n> I didn't look into detail, but this looks like it's writing a single\n> object. In particular, it can convert OFS into REF, something that the\n> existing code cannot do.\n\nRight, that was an easy thing to do once we started actually walking\nover the set of objects. The old code just tried to dump a whole segment\nof the pack verbatim. That's faster than the traditional way of actually\nadding objects to the packing list, but it didn't kick in very often.\nThis new code is really going for a middle ground: do _some_ per-object\nwork, but way less than we'd traditionally do.\n\nBy the way, that's another possible solution for the offset problem:\nconvert everything after the first gap to REF_DELTA. But the resulting\npack is larger and slightly less efficient for the client to use. And I\ndon't know that it's actually cheaper to generate than just adjusting\nthe offset (for each OFS_DELTA, you have to compute the offset of its\nbase and then do a revindex lookup to find the actual sha1 to write).\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\tdisplay_progress(progress_state, written);\n> > \t}\n> > +\treturn pos;\n> > +}\n> \n> I presume this optimization is needed for the case where we are using\n> *all* objects of a packfile, as is typical during a clone.\n\nIt's not strictly needed, but yeah. If we know we're sending the first N\nobjects of the pack, then we don't even have to look at them. We can\njust dump the bytes, and start our per-object traversal at N+1. That\nshould make it just as fast as the original pack-reuse code for this\ncase.\n\n> > @@ -1002,6 +1132,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> Hmm...why did we previously not need to check the reuse information, but\n> we do now? I gave the code a cursory glance but couldn't find the\n> answer.\n\nI think the original code may simply have been buggy and nobody noticed.\nHere's what I wrote when this line was added in our fork:\n\n pack-objects: check reused pack bitmap for duplicate objects\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 this\n 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\nI'm not sure why we didn't notice it with the older reuse code. It may\nsimply have been that it hardly ever triggered on our servers.\n\n> > static int obj_is_packed(const struct object_id *oid)\n> > {\n> > -\treturn !!packlist_find(&to_pack, oid, NULL);\n> > +\treturn packlist_find(&to_pack, oid, NULL) ||\n> > +\t\t(reuse_packfile_bitmap &&\n> > +\t\t bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid));\n> \n> Same question here - why do we need to check the reuse information?\n\nThis was added earlier than the call above. It's meant to handle\ninclude-tag as well. Again, I'm not sure why the earlier reuse code\ndidn't need that, and I'd suspect it may simply be buggy.\n\n> > @@ -3061,7 +3199,6 @@ static void loosen_unused_packed_objects(void)\n> > static int pack_options_allow_reuse(void)\n> > {\n> > \treturn 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> \n> Relaxing of the allow_ofs_delta condition - makes sense given (as above)\n> we can convert OFS to REF.\n\nYep, exactly.\n\n> Overall I think that this makes sense, except for my unanswered\n> questions (and the presence of reused_chunk).\n\nThanks for looking at it. I still have to take a careful pass over the\nwhole split, but I've tried to at least answer your questions in the\nmeantime.\n\n-Peff\n"},{"id":"383913","messageId":"20191011180507.GB20601@sigill.intra.peff.net","threadId":"51843","inReplyTo":"CAP8UFD0-NHCj6KcbdMG3bCwWp=wUdoYugLggsbnpvr1d6-P4yg@mail.gmail.com","subject":"Re: [RFC PATCH 04/10] ewah/bitmap: always allocate 2 more words","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-11T18:05:07Z","receivedAt":"2019-10-11T18:05:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 11, 2019 at 09:49:53AM +0200, Christian Couder wrote:\n\n> > I think this should be squashed with patch 3, adding to that commit\n> > message \"since word_alloc might be 0, we need to change the growth\n> > function\". (Or just make the minimum word_alloc be 1 or 32 or something\n> > positive, if that's possible.)\n> \n> Yeah, thank you for the suggestion. I still wonder why 2 is added\n> instead of just 1 though.\n\nYeah, I think it should be squashed. I think it is not intentionally 2,\nit is just that adding \"1\" to block makes sure we always make forward\nprogress. It could equally well be:\n\n self->word_alloc = block ? block * 2 : 1;\n\nI think. Or probably this whole thing could be ALLOC_GROW(), as the\nnumbers aren't particularly important. I guess we need to make sure the\ngrown part is zero'd, so probably using alloc_nr() directly would make\nmore sense.\n\n-Peff\n"},{"id":"383935","messageId":"20191011210434.140296-1-jonathantanmy@google.com","threadId":"51843","inReplyTo":"20191011180125.GA20601@sigill.intra.peff.net","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Jonathan Tan","fromEmail":"jonathantanmy@google.com","sentAt":"2019-10-11T21:04:34Z","receivedAt":"2019-10-11T21:04:39Z","isPatch":true,"sender":{"key":"jonathantanmy@fastmail.com","avatar":null},"body":"> > This makes sense - offsets may be different when we omit objects from\n> > the packfile. I think this can be computed by calculating the number of\n> > zero bits between the current object's index and the nth object prior\n> > (where n is the offset) in the bitmap resulting from\n> > reuse_partial_packfile_from_bitmap() above, thus eliminating the need\n> > for this array, but I haven't tested it.\n> \n> You need to know not just the number of zero bits, but the accumulated\n> offset due to those missing objects. So you'd end up having to walk over\n> the revindex for that set of objects. This array is basically caching\n> those accumulated offsets (for the parts we _do_ include) so we don't\n> have to compute them repeatedly.\n\nAh...yes. For some reason I thought that the offset was a number of\nobjects, but it is actually a number of bytes. The patch makes sense\nnow.\n\n> There's also a more subtle issue with entry sizes; see below.\n\nGood point.\n\n> > > @@ -1002,6 +1132,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> > Hmm...why did we previously not need to check the reuse information, but\n> > we do now? I gave the code a cursory glance but couldn't find the\n> > answer.\n> \n> I think the original code may simply have been buggy and nobody noticed.\n> Here's what I wrote when this line was added in our fork:\n\n[snip explanation]\n\nThanks - I'll also take a look if I have time.\n\n> Thanks for looking at it. I still have to take a careful pass over the\n> whole split, but I've tried to at least answer your questions in the\n> meantime.\n\nThanks for your responses. Also thanks to Christian for splitting it in\nthe first place, making it easier to review.\n"},{"id":"383952","messageId":"xmqqsgnyg76d.fsf@gitster-ct.c.googlers.com","threadId":"51843","inReplyTo":"20191011180125.GA20601@sigill.intra.peff.net","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-10-12T00:04:58Z","receivedAt":"2019-10-12T00:07:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> The current code does so by creating a new entry in the reused_chunks\n> array. In the worst case that can grow to have the same number of\n> entries as we have objects. So this code was an attempt to pad the\n> header of a shrunken entry to keep it the same size. I don't remember\n> all the problems we ran into with that, but in the end we found that it\n> didn't actually help much, because in practice we don't end up with a\n> lot of chunks anyway.\n\nHmm, I am kind of surprised that the decoding side allowed such a\npadding.\n\n> For instance, packing torvalds/linux on our servers just now reused 6.5M\n> objects, but only needed ~50k chunks.\n\nOK, that's a good argument for not trying to optimize.\n\n> I think the original code may simply have been buggy and nobody noticed.\n> Here's what I wrote when this line was added in our fork:\n>\n> pack-objects: check reused pack bitmap for duplicate objects\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 this\n> 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> I'm not sure why we didn't notice it with the older reuse code. It may\n> simply have been that it hardly ever triggered on our servers.\n\nImpressed by the careful thinking here.\n\nThanks.\n"},{"id":"383989","messageId":"20191013073851.GA7001@sigill.intra.peff.net","threadId":"51843","inReplyTo":"xmqqsgnyg76d.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-13T07:38:52Z","receivedAt":"2019-10-13T07:38:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Oct 12, 2019 at 09:04:58AM +0900, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > The current code does so by creating a new entry in the reused_chunks\n> > array. In the worst case that can grow to have the same number of\n> > entries as we have objects. So this code was an attempt to pad the\n> > header of a shrunken entry to keep it the same size. I don't remember\n> > all the problems we ran into with that, but in the end we found that it\n> > didn't actually help much, because in practice we don't end up with a\n> > lot of chunks anyway.\n> \n> Hmm, I am kind of surprised that the decoding side allowed such a\n> padding.\n\nIIRC, the \"padding\" is just a sequence of 0-length-plus-continuation-bit\nvarint bytes. And for some reason it worked for the size but not for the\ndelta offset value. So the decoder wasn't aware of it, but simply hadn't\nexplicitly enforced that there weren't pointless bytes.\n\nBut yeah, it seems like a pretty hacky thing to rely on. I don't think\nwe ever even ran that code in production, and the if(0) was just\nleftover experimental cruft.\n\n> > I think the original code may simply have been buggy and nobody noticed.\n> > Here's what I wrote when this line was added in our fork:\n> [...]\n> Impressed by the careful thinking here.\n\nIt's unfortunate that the reasoning there wasn't part of the earlier\nsubmission. I'm not sure how to reconcile that. The patches as\noriginally written can't be applied now (they were munged over the years\nduring merges with upstream). And some of them are just \"oops, fix this\ndumb bug\" trash that we wouldn't want to take anyway.\n\nSo I think at best they're something for somebody to manually look at\nand try to incorporate into the commit messages of the revised patch\nseries. But I didn't give them to Christian to work with because it's\nhard to even figure out which patches are still relevant. I wish I had a\nbetter tooling there. I've been playing with something that looks at a\ndiff and then tries to blame each of the touched lines. Which is sort of\nlike the \"-L\" line-log, I guess, but for a very non-contiguous set of\nlines.\n\n-Peff\n"},{"id":"384243","messageId":"xmqq8spj97mj.fsf@gitster-ct.c.googlers.com","threadId":"51843","inReplyTo":"20191013073851.GA7001@sigill.intra.peff.net","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2019-10-17T07:03:00Z","receivedAt":"2019-10-17T07:04:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n>> Hmm, I am kind of surprised that the decoding side allowed such a\n>> padding.\n>\n> IIRC, the \"padding\" is just a sequence of 0-length-plus-continuation-bit\n> varint bytes. And for some reason it worked for the size but not for the\n> delta offset value.\n\nI think the reason is because they use different varint definition.\n\nThe encoding used in builtin/pack-objects.c::write_no_reuse_object()\nis for offsets, and it came much later and with an improvement over\nthe encoding used for delta size in diff-delta.c::create_delta().\nThe more recent encoding does not allow padding (when I compare the\ndecoders for these two encodings, I notice there is +1 for each\n7-bit iteration; this essentially declares that a byte with \"not the\nfinal byte\" bit set with all other bits clear does not mean 0 but it\nmeans 1, which breaks the idea of padding to encode filler zero\nbits).\n"},{"id":"384246","messageId":"20191017072326.GA14045@sigill.intra.peff.net","threadId":"51843","inReplyTo":"xmqq8spj97mj.fsf@gitster-ct.c.googlers.com","subject":"Re: [RFC PATCH 10/10] pack-objects: improve partial packfile reuse","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-10-17T07:23:26Z","receivedAt":"2019-10-17T07:25:10Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 17, 2019 at 04:03:00PM +0900, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> >> Hmm, I am kind of surprised that the decoding side allowed such a\n> >> padding.\n> >\n> > IIRC, the \"padding\" is just a sequence of 0-length-plus-continuation-bit\n> > varint bytes. And for some reason it worked for the size but not for the\n> > delta offset value.\n> \n> I think the reason is because they use different varint definition.\n> \n> The encoding used in builtin/pack-objects.c::write_no_reuse_object()\n> is for offsets, and it came much later and with an improvement over\n> the encoding used for delta size in diff-delta.c::create_delta().\n> The more recent encoding does not allow padding (when I compare the\n> decoders for these two encodings, I notice there is +1 for each\n> 7-bit iteration; this essentially declares that a byte with \"not the\n> final byte\" bit set with all other bits clear does not mean 0 but it\n> means 1, which breaks the idea of padding to encode filler zero\n> bits).\n\nYeah, that sounds right. I think the \"old\" one is actually the pack size\nheader in unpack_object_header_buffer(), not the delta size header.\n\nAt any rate, it seems like a terrible idea, so I'll be glad to see the\ncode dropped. :)\n\n-Peff\n"}]}