{"thread":{"id":"51531","subject":"Reporting reused packfile objects","startedAt":"2019-07-26T18:11:03Z","lastAt":"2019-07-28T23:02:11Z","messageCount":2,"participants":["James Ramsay","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"379379","messageId":"3E56B0FD-EBE8-4057-A93A-16EBB09FBCE0@jramsay.com.au","threadId":"51531","inReplyTo":null,"subject":"Reporting reused packfile objects","fromName":"James Ramsay","fromEmail":"james@jramsay.com.au","sentAt":"2019-07-26T18:10:58Z","receivedAt":"2019-07-26T18:11:03Z","isPatch":false,"sender":{"key":"james@jramsay.com.au","avatar":null},"body":"While investigating improvements to clone performance at GitLab we've \nbeen looking at how to trigger packfile reuse during clones. A challenge \nof the investigation and a future challenge of rolling out changes to \nencourage more frequent packfile reuse is knowing when packfile reuse \nkicks in and the extent of the reuse.\n\nI notice that GitHub outputs 'pack-reused' statistics when fetching. I \nassume this is for similar reasons.\n\nWould there be interest in including a reused packfile objects statistic \nin the output of upload-pack?\n\nI'm happy to contribute a patch (it is quite a small change), but it \nmight be more efficient to upstream the patch that GitHub appears to \nalready be running in production. Peff, what do you think?\n\nThanks,\nJames\n"},{"id":"379455","messageId":"20190728230205.GB21379@sigill.intra.peff.net","threadId":"51531","inReplyTo":"3E56B0FD-EBE8-4057-A93A-16EBB09FBCE0@jramsay.com.au","subject":"Re: Reporting reused packfile objects","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-07-28T23:02:05Z","receivedAt":"2019-07-28T23:02:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 26, 2019 at 02:10:58PM -0400, James Ramsay wrote:\n\n> While investigating improvements to clone performance at GitLab we've been\n> looking at how to trigger packfile reuse during clones. A challenge of the\n> investigation and a future challenge of rolling out changes to encourage\n> more frequent packfile reuse is knowing when packfile reuse kicks in and the\n> extent of the reuse.\n> \n> I notice that GitHub outputs 'pack-reused' statistics when fetching. I\n> assume this is for similar reasons.\n\nYeah, we (GitHub) added it long ago when looking at why and when reuse\nkicked in (or didn't).\n\nWhat we found is that the initial implementation (which we did!) made a\nlot of bad assumptions. The absolute worst one (for us, but also for\nanyone else who follows our one-big-pack-for-all-forks approach) is\nmeasuring the percentage of the total pack that's going to be sent. In a\nworld where you have a bunch of objects from other forks in the pack,\nit's normal and expected that you'd be sending a much smaller percentage\nof the pack.\n\nIn the end we rewrote that whole section of the code to be a lot\nsmarter. It allows \"holes\" in the chunks of packfile to be reused, and\nskips over them. It rewrites OFS_DELTA offsets as it goes to account for\nthe holes. So it's basically a linear walk over the packfile, but with\nthe important distinction that we don't add those objects to the\nobject_entry array, which makes them very lightweight (especially in\nmemory use, but they also aren't considered bases for finding new\ndeltas, etc). I don't have exact numbers handy, but it seems like a good\ncompromise between the cost to serve a clone and the quality of the\nresulting packfile.\n\nIt's been on my todo list to upstream for a while, but I've dragged my\nfeet on it because there's a lot of cleanup/polishing from the original\npatches (they were never very clean in the first place, and we've merged\na dozen or more times with upstream since then, so the updates are\nspread across a bunch of merge commits).\n\n> Would there be interest in including a reused packfile objects statistic in\n> the output of upload-pack?\n> \n> I'm happy to contribute a patch (it is quite a small change), but it might\n> be more efficient to upstream the patch that GitHub appears to already be\n> running in production. Peff, what do you think?\n\nYeah, I think we should work on getting our changes (including those\nstats) into upstream.\n\nI'll look into turning this into a readable series, but in the meantime,\nhere's a _very_ rough diff against the current tip of master. I say\nrough because we have other pack and bitmap-related changes, too. This\nis the result of me spending a few minutes manually picking out hunks to\nthe point that \"make test\" seems to work. No guarantees beyond that\n(yet). ;)\n\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\ndiff --git a/builtin/pack-objects.c b/builtin/pack-objects.c\nindex 267c562b1f..497f61723e 100644\n--- a/builtin/pack-objects.c\n+++ b/builtin/pack-objects.c\n@@ -92,10 +92,11 @@ 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+static int allow_pack_reuse = 1;\n static int write_bitmap_index;\n static uint16_t write_bitmap_options = BITMAP_OPT_HASH_CACHE;\n \n@@ -780,57 +781,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-\tclose(fd);\n-\twritten = reuse_packfile_objects;\n-\tdisplay_progress(progress_state, written);\n-\treturn reuse_packfile_offset - sizeof(struct pack_header);\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 \n static const char no_split_warning[] = N_(\n@@ -863,11 +996,9 @@ static void write_pack_file(void)\n \t\toffset = write_pack_header(f, nr_remaining);\n \n \t\tif (reuse_packfile) {\n-\t\t\toff_t packfile_size;\n \t\t\tassert(pack_to_stdout);\n-\n-\t\t\tpackfile_size = write_reused_pack(f);\n-\t\t\toffset += packfile_size;\n+\t\t\twrite_reused_pack(f);\n+\t\t\toffset = hashfile_total(f);\n \t\t}\n \n \t\tnr_written = 0;\n@@ -996,6 +1127,10 @@ static int have_duplicate_entry(const struct object_id *oid,\n {\n \tstruct object_entry *entry;\n \n+\tif (reuse_packfile_bitmap &&\n+\t    bitmap_walk_contains(bitmap_git, reuse_packfile_bitmap, oid))\n+\t\treturn 1;\n+\n \tentry = packlist_find(&to_pack, oid, index_pos);\n \tif (!entry)\n \t\treturn 0;\n@@ -1185,6 +1320,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@@ -2562,6 +2698,13 @@ 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+\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 {\n \tstruct tag *tag;\n@@ -2573,7 +2716,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@@ -2597,7 +2740,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@@ -2665,6 +2808,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@@ -2713,6 +2857,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@@ -3045,7 +3193,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@@ -3057,12 +3204,13 @@ 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 \t\t\t&reuse_packfile_objects,\n-\t\t\t&reuse_packfile_offset)) {\n+\t\t\t&reuse_packfile_bitmap)) {\n \t\tassert(reuse_packfile_objects);\n \t\tnr_result += reuse_packfile_objects;\n \t\tdisplay_progress(progress_state, nr_result);\n@@ -3514,7 +3662,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 }\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));\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 52f1178db4..9e3227f215 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -22,21 +22,26 @@\n #define EWAH_MASK(x) ((eword_t)1 << (x % BITS_IN_EWORD))\n #define EWAH_BLOCK(x) (x / BITS_IN_EWORD)\n \n-struct bitmap *bitmap_new(void)\n+struct bitmap *bitmap_new2(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_new2(32);\n+}\n+\n void bitmap_set(struct bitmap *self, size_t pos)\n {\n \tsize_t block = EWAH_BLOCK(pos);\n \n \tif (block >= self->word_alloc) {\n \t\tsize_t old_size = self->word_alloc;\n-\t\tself->word_alloc = block * 2;\n+\t\tself->word_alloc = (block + 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));\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex 84b2a29faa..3ff650c5cd 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_new2(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);\ndiff --git a/pack-bitmap.c b/pack-bitmap.c\nindex ed2befaac6..3202ea1148 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@@ -622,7 +629,7 @@ static void show_objects_for_type(\n \tenum object_type object_type,\n \tshow_reachable_fn show_reach)\n {\n-\tsize_t pos = 0, i = 0;\n+\tsize_t i = 0;\n \tuint32_t offset;\n \n \tstruct ewah_iterator it;\n@@ -630,13 +637,15 @@ static void show_objects_for_type(\n \n \tstruct bitmap *objects = bitmap_git->result;\n \n-\tif (bitmap_git->reuse_objects == bitmap_git->pack->num_objects)\n-\t\treturn;\n-\n \tewah_iterator_init(&it, type_filter);\n \n-\twhile (i < objects->word_alloc && ewah_iterator_next(&filter, &it)) {\n+\tfor (i = 0; i < objects->word_alloc &&\n+\t\t\tewah_iterator_next(&filter, &it); i++) {\n \t\teword_t word = objects->words[i] & filter;\n+\t\tsize_t pos = (i * BITS_IN_EWORD);\n+\n+\t\tif (!word)\n+\t\t\tcontinue;\n \n \t\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n \t\t\tstruct object_id oid;\n@@ -648,9 +657,6 @@ static void show_objects_for_type(\n \n \t\t\toffset += ewah_bit_ctz64(word >> offset);\n \n-\t\t\tif (pos + offset < bitmap_git->reuse_objects)\n-\t\t\t\tcontinue;\n-\n \t\t\tentry = &bitmap_git->pack->revindex[pos + offset];\n \t\t\tnth_packed_object_oid(&oid, bitmap_git->pack, entry->nr);\n \n@@ -659,9 +665,6 @@ static void show_objects_for_type(\n \n \t\t\tshow_reach(&oid, object_type, 0, hash, bitmap_git->pack, entry->offset);\n \t\t}\n-\n-\t\tpos += BITS_IN_EWORD;\n-\t\ti++;\n \t}\n }\n \n@@ -770,66 +773,139 @@ struct bitmap_index *prepare_bitmap_walk(struct rev_info *revs)\n \treturn NULL;\n }\n \n-int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n-\t\t\t\t       struct packed_git **packfile,\n-\t\t\t\t       uint32_t *entries,\n-\t\t\t\t       off_t *up_to)\n+static void try_partial_reuse(struct bitmap_index *bitmap_git,\n+\t\t\t      size_t pos,\n+\t\t\t      struct bitmap *reuse,\n+\t\t\t      struct pack_window **w_curs)\n {\n+\tstruct revindex_entry *revidx;\n+\toff_t offset;\n+\tenum object_type type;\n+\tunsigned long size;\n+\n+\tif (pos >= bitmap_git->pack->num_objects)\n+\t\treturn; /* not actually in the pack */\n+\n+\trevidx = &bitmap_git->pack->revindex[pos];\n+\toffset = revidx->offset;\n+\ttype = unpack_object_header(bitmap_git->pack, w_curs, &offset, &size);\n+\tif (type < 0)\n+\t\treturn; /* broken packfile, punt */\n+\n+\tif (type == OBJ_REF_DELTA || type == OBJ_OFS_DELTA) {\n+\t\toff_t base_offset;\n+\t\tint base_pos;\n+\n+\t\t/*\n+\t\t * Find the position of the base object so we can look it up\n+\t\t * in our bitmaps. If we can't come up with an offset, or if\n+\t\t * that offset is not in the revidx, the pack is corrupt.\n+\t\t * There's nothing we can do, so just punt on this object,\n+\t\t * and the normal slow path will complain about it in\n+\t\t * more detail.\n+\t\t */\n+\t\tbase_offset = get_delta_base(bitmap_git->pack, w_curs,\n+\t\t\t\t\t     &offset, type, revidx->offset);\n+\t\tif (!base_offset)\n+\t\t\treturn;\n+\t\tbase_pos = find_revindex_position(bitmap_git->pack, base_offset);\n+\t\tif (base_pos < 0)\n+\t\t\treturn;\n+\n+\t\t/*\n+\t\t * We assume delta dependencies always point backwards. This\n+\t\t * lets us do a single pass, and is basically always true\n+\t\t * due to the way OFS_DELTAs work. You would not typically\n+\t\t * find REF_DELTA in a bitmapped pack, since we only bitmap\n+\t\t * packs we write fresh, and OFS_DELTA is the default). But\n+\t\t * let's double check to make sure the pack wasn't written with\n+\t\t * odd parameters.\n+\t\t */\n+\t\tif (base_pos >= pos)\n+\t\t\treturn;\n+\n+\t\t/*\n+\t\t * And finally, if we're not sending the base as part of our\n+\t\t * reuse chunk, then don't send this object either. The base\n+\t\t * would come after us, along with other objects not\n+\t\t * necessarily in the pack, which means we'd need to convert\n+\t\t * to REF_DELTA on the fly. Better to just let the normal\n+\t\t * object_entry code path handle it.\n+\t\t */\n+\t\tif (!bitmap_get(reuse, base_pos))\n+\t\t\treturn;\n+\t}\n+\n \t/*\n-\t * Reuse the packfile content if we need more than\n-\t * 90% of its objects\n+\t * If we got here, then the object is OK to reuse. Mark it.\n \t */\n-\tstatic const double REUSE_PERCENT = 0.9;\n+\tbitmap_set(reuse, pos);\n+}\n \n+int reuse_partial_packfile_from_bitmap(struct bitmap_index *bitmap_git,\n+\t\t\t\t       struct packed_git **packfile_out,\n+\t\t\t\t       uint32_t *entries,\n+\t\t\t\t       struct bitmap **reuse_out)\n+{\n \tstruct bitmap *result = bitmap_git->result;\n-\tuint32_t reuse_threshold;\n-\tuint32_t i, reuse_objects = 0;\n+\tstruct bitmap *reuse;\n+\tstruct pack_window *w_curs = NULL;\n+\tsize_t i = 0;\n+\tuint32_t offset;\n \n \tassert(result);\n \n-\tfor (i = 0; i < result->word_alloc; ++i) {\n-\t\tif (result->words[i] != (eword_t)~0) {\n-\t\t\treuse_objects += ewah_bit_ctz64(~result->words[i]);\n-\t\t\tbreak;\n-\t\t}\n+\twhile (i < result->word_alloc && result->words[i] == (eword_t)~0)\n+\t\ti++;\n \n-\t\treuse_objects += BITS_IN_EWORD;\n-\t}\n+\t/* Don't mark objects not in the packfile */\n+\tif (i > bitmap_git->pack->num_objects / BITS_IN_EWORD)\n+\t\ti = bitmap_git->pack->num_objects / BITS_IN_EWORD;\n \n-#ifdef GIT_BITMAP_DEBUG\n-\t{\n-\t\tconst unsigned char *sha1;\n-\t\tstruct revindex_entry *entry;\n+\treuse = bitmap_new2(i);\n+\tmemset(reuse->words, 0xFF, i * sizeof(eword_t));\n \n-\t\tentry = &bitmap_git->reverse_index->revindex[reuse_objects];\n-\t\tsha1 = nth_packed_object_sha1(bitmap_git->pack, entry->nr);\n+\tfor (; i < result->word_alloc; ++i) {\n+\t\teword_t word = result->words[i];\n+\t\tsize_t pos = (i * BITS_IN_EWORD);\n \n-\t\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\tfor (offset = 0; offset < BITS_IN_EWORD; ++offset) {\n+\t\t\tif ((word >> offset) == 0)\n+\t\t\t\tbreak;\n+\n+\t\t\toffset += ewah_bit_ctz64(word >> offset);\n+\t\t\ttry_partial_reuse(bitmap_git, pos + offset, reuse, &w_curs);\n+\t\t}\n \t}\n-#endif\n \n-\tif (!reuse_objects)\n-\t\treturn -1;\n+\tunuse_pack(&w_curs);\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*entries = bitmap_popcount(reuse);\n+\tif (!*entries) {\n+\t\tbitmap_free(reuse);\n+\t\treturn -1;\n \t}\n \n-\treuse_threshold = bitmap_popcount(bitmap_git->result) * REUSE_PERCENT;\n+\t/*\n+\t * Drop any reused objects from the result, since they will not\n+\t * need to be handled separately.\n+\t */\n+\tbitmap_and_not(result, reuse);\n+\t*packfile_out = bitmap_git->pack;\n+\t*reuse_out = reuse;\n+\treturn 0;\n+}\n \n-\tif (reuse_objects < reuse_threshold)\n-\t\treturn -1;\n+int bitmap_walk_contains(struct bitmap_index *bitmap_git,\n+                        struct bitmap *bitmap, const struct object_id *oid)\n+{\n+       int idx;\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+       if (!bitmap)\n+               return 0;\n \n-\treturn 0;\n+       idx = bitmap_position(bitmap_git, oid);\n+       return idx >= 0 && bitmap_get(bitmap, idx);\n }\n \n void traverse_bitmap_commit_list(struct bitmap_index *bitmap_git,\ndiff --git a/pack-bitmap.h b/pack-bitmap.h\nindex 00de3ec8e4..7af7335f2e 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@@ -49,10 +50,13 @@ 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+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\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.22.0.1052.g5dbc04cce0\n\n"}]}