[PATCH v2 0/9] Rewrite packfile reuse code

This patch series is rewriting the code that tries to reuse existing packfiles.

The code in this patch series was written by GitHub, and Peff nicely provided it in the following discussion:

https://public-inbox.org/git/3E56B0FD-EBE8-4057-A93A-16EBB09FBCE0@jramsay.com.au/

The first version of this patch series was also discussed:

https://public-inbox.org/git/20190913130226.7449-1-chriscool@tuxfamily.org/

Thanks to the reviewers!

According to Peff this new code is a lot smarter than what it replaces. It allows "holes" in the chunks of packfile to be reused, and skips over them. It rewrites OFS_DELTA offsets as it goes to account for the holes. So it's basically a linear walk over the packfile, but with the important distinction that we don't add those objects to the object_entry array, which makes them very lightweight (especially in memory use, but they also aren't considered bases for finding new deltas, etc). It seems like a good compromise between the cost to serve a clone and the quality of the resulting packfile.

Changes since the previous patch series are the following:

  - Rebased onto current master (v2.24.0-rc0), which means that
    conflicts due to dropping the last argument of packlist_find() are
    resolved.

  - Replaced "in a following patch" with "in a following commit" in
    commit messages.

  - Squashed previous patchs 3/10 and 4/10 into new patch 3/9 as
    suggested by Peff and Jonathan.

  - Changed commit message of patch 3/9, so that the justification
    should be correct now.

  - Also in patch 3/9, `block ? block * 2 : 1` is now used to compute
    the number of words that should be allocated.

  - Changed commit message of patch 4/9 (previously 5/10), so that the
    justification should be correct now.

  - Document pack.allowPackReuse in patch 7/9.

  - Also in patch 7/9 move using the `allow_pack_reuse` variable into
    pack_options_allow_reuse() as suggested by Junio.

  - Improved commit message in patch 9/9 a lot by adding many comments
    made by Peff about it.

  - In patch 9/9 removed `if (0) { ... }` code.

  - Also in patch 9/9 changed parameter name from
    `struct bitmap **bitmap` to `struct bitmap **reuse_out` in
    pack-bitmap.h as suggested by Jonathan.

I tried to use `git range-diff` to see if I could send its output to compare this patch series with the previous one, but it looks like it unfortunately thinks that new patch 7/9 is completely different than previous patch 8/10, and also it shows a lot more changes from patch 10/10 to patch 9/9 than necessary for some reason. So I decided not to send it, but if you want it anyway please tell me.

I have put Peff as the author of all the commits.

Jeff King (9):
  builtin/pack-objects: report reused packfile objects
  packfile: expose get_delta_base()
  ewah/bitmap: introduce bitmap_word_alloc()
  pack-bitmap: don't rely on bitmap_git->reuse_objects
  pack-bitmap: introduce bitmap_walk_contains()
  csum-file: introduce hashfile_total()
  pack-objects: introduce pack.allowPackReuse
  builtin/pack-objects: introduce obj_is_packed()
  pack-objects: improve partial packfile reuse

 Documentation/config/pack.txt |   4 +
 builtin/pack-objects.c        | 235 +++++++++++++++++++++++++++-------
 csum-file.h                   |   9 ++
 ewah/bitmap.c                 |  13 +-
 ewah/ewok.h                   |   1 +
 pack-bitmap.c                 | 178 +++++++++++++++++--------
 pack-bitmap.h                 |   6 +-
 packfile.c                    |  10 +-
 packfile.h                    |   3 +
 9 files changed, 349 insertions(+), 110 deletions(-)