git/pack-bitmap.c, branch v2.33.6

Merge branch 'jk/check-pack-valid-before-opening-bitmap'

2021-08-02T21:06:43Z

A race between repacking and using pack bitmaps has been corrected. * jk/check-pack-valid-before-opening-bitmap: pack-bitmap: check pack validity when opening bitmap

Merge branch 'tb/bitmap-type-filter-comment-fix'

2021-08-02T21:06:38Z

In-code comment update. * tb/bitmap-type-filter-comment-fix: pack-bitmap: clarify comment in filter_bitmap_exclude_type()

pack-bitmap: check pack validity when opening bitmap

2021-07-23T18:37:56Z

When pack-objects adds an entry to its list of objects to pack, it may mark the packfile and offset that contains the file, which we can later use to output the object verbatim. If the packfile is deleted while we are running (e.g., by another process running "git repack"), we may die in use_pack() if the pack file cannot be opened. We worked around this in 4c08018204 (pack-objects: protect against disappearing packs, 2011-10-14) by making sure we can open the pack before recording it as a source. This detects a pack which has already disappeared while generating the packing list, and because we keep the pack's file descriptor (or an mmap window) open, it means we can access it later (unless you exceed core.packedgitlimit). The bitmap code that was added later does not do this; it adds entries to the packlist without checking that the packfile is still valid, and is vulnerable to this race. It needs the same treatment as 4c08018204. However, rather than add it in just that one spot, it makes more sense to simply open and check the packfile when we open the bitmap. Technically you can use the .bitmap without even looking in the .pack file (e.g., if you are just printing a list of objects without accessing them), but it's much simpler to do it early. That covers all later direct uses of the pack (due to the cached descriptor) without having to check each one directly. For example, in pack-objects we need to protect the packlist entries, but we also access the pack directly as part of the reuse_partial_pack_from_bitmap() feature. This patch covers both cases. There's no test here, because the problem is inherently racy. I reproduced and verified the fix with this script: rm -rf parent.git push.git fetch.git push() { ( cd push.git && echo content >>file && git add file && git commit -qm "change $1" && git push -q origin HEAD && echo "push $1..." ) && ( cd parent.git && git repack -ad -q && echo "repack $1..." ) } fetch() { rm -rf fetch.git && git clone -q file://$PWD/parent.git fetch.git && echo "fetch $1..." } git init --bare parent.git && git --git-dir=parent.git config transfer.unpacklimit 1 && git clone parent.git push.git && (for i in `seq 1 1000`; do push $i || break; done) & pusher=$! (for i in `seq 1 1000`; do fetch $i || break; done) & fetcher=$! wait $fetcher kill $pusher That simulates a race between a client cloning and a push triggering a repack on the server. Without this patch, it generally fails within a couple hundred iterations with: remote: fatal: packfile ./objects/pack/.tmp-1377349-pack-498afdec371232bdb99d1757872f5569331da61e.pack cannot be accessed error: git upload-pack: git-pack-objects died with error. fatal: git upload-pack: aborting due to possible repository corruption on the remote side. remote: aborting due to possible repository corruption on the remote side. fatal: early EOF fatal: fetch-pack: invalid index-pack output With this patch, it reliably runs through all thousand attempts. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano

pack-bitmap: clarify comment in filter_bitmap_exclude_type()

2021-07-20T22:04:07Z

The code that eventually became filter_bitmap_exclude_type() was originally introduced in 4f3bd5606a (pack-bitmap: implement BLOB_NONE filtering, 2020-02-14) to accelerate BLOB_NONE filters with bitmaps. In 856e12c18a (pack-bitmap.c: make object filtering functions generic, 2020-05-04), it became filter_bitmap_exclude_type(). But not all of the comments were updated to be agnostic to the provided type. Remove the remaining comments which should have been updated in 856e12c18a to reflect the type-agnostic nature of the function. Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

bitmaps: don't recurse into trees already in the bitmap

2021-06-15T02:13:11Z

If an object is already mentioned in a reachability bitmap we are building, then by definition so are all of the objects it can reach. We have an optimization to stop traversing commits when we see they are already in the bitmap, but we don't do the same for trees. It's generally unavoidable to recurse into trees for commits not yet covered by bitmaps (since most commits generally do have unique top-level trees). But they usually have subtrees that are shared with other commits (i.e., all of the subtrees the commit _didn't_ touch). And some of those commits (and their trees) may be covered by the bitmap. Usually this isn't _too_ big a deal, because we'll visit those subtrees only once in total for the whole walk. But if you have a large number of unbitmapped commits, and if your tree is big, then you may end up opening a lot of sub-trees for no good reason. We can use the same optimization we do for commits here: when we are about to open a tree, see if it's in the bitmap (either the one we are building, or the "seen" bitmap which covers the UNINTERESTING side of the bitmap when doing a set-difference). This works especially well because we'll visit all commits before hitting any trees. So even in a history like: A -- B if "A" has a bitmap on disk but "B" doesn't, we'll already have OR-ed in the results from A before looking at B's tree (so we really will only look at trees touched by B). For most repositories, the timings produced by p5310 are unspectacular. Here's linux.git: Test HEAD^ HEAD -------------------------------------------------------------------- 5310.4: simulated clone 6.00(5.90+0.10) 5.98(5.90+0.08) -0.3% 5310.5: simulated fetch 2.98(5.45+0.18) 2.85(5.31+0.18) -4.4% 5310.7: rev-list (commits) 0.32(0.29+0.03) 0.33(0.30+0.03) +3.1% 5310.8: rev-list (objects) 1.48(1.44+0.03) 1.49(1.44+0.05) +0.7% Any improvement there is within the noise (the +3.1% on test 7 has to be noise, since we are not recursing into trees, and thus the new code isn't even run). The results for git.git are likewise uninteresting. But here are numbers from some other real-world repositories (that are not public). This one's tree is comparable in size to linux.git, but has ~16k refs (and so less complete bitmap coverage): Test HEAD^ HEAD ------------------------------------------------------------------------- 5310.4: simulated clone 38.34(39.86+0.74) 33.95(35.53+0.76) -11.5% 5310.5: simulated fetch 2.29(6.31+0.35) 2.20(5.97+0.41) -3.9% 5310.7: rev-list (commits) 0.99(0.86+0.13) 0.96(0.85+0.11) -3.0% 5310.8: rev-list (objects) 11.32(11.04+0.27) 6.59(6.37+0.21) -41.8% And here's another with a very large tree (~340k entries), and a fairly large number of refs (~10k): Test HEAD^ HEAD ------------------------------------------------------------------------- 5310.3: simulated clone 53.83(54.71+1.54) 39.77(40.76+1.50) -26.1% 5310.4: simulated fetch 19.91(20.11+0.56) 19.79(19.98+0.67) -0.6% 5310.6: rev-list (commits) 0.54(0.44+0.11) 0.51(0.43+0.07) -5.6% 5310.7: rev-list (objects) 24.32(23.59+0.73) 9.85(9.49+0.36) -59.5% This patch provides substantial improvements in these larger cases, and have any drawbacks for smaller ones (the cost of the bitmap check is quite small compared to an actual tree traversal). Note that we have to add a version of revision.c's include_check callback which handles non-commits. We could possibly consolidate this into a single callback for all objects types, as there's only one user of the feature which would need converted (pack-bitmap.c:should_include). That would in theory let us avoid duplicating any logic. But when I tried it, the code ended up much worse to read, with lots of repeated "if it's a commit do this, otherwise do that". Having two separate callbacks splits that naturally, and matches the existing split of show_commit/show_object callbacks. Signed-off-by: Jeff King Signed-off-by: Junio C Hamano

Merge branch 'ps/rev-list-object-type-filter'

2021-05-07T03:47:41Z

"git rev-list" learns the "--filter=object:type=" option, which can be used to exclude objects of the given kind from the packfile generated by pack-objects. * ps/rev-list-object-type-filter: rev-list: allow filtering of provided items pack-bitmap: implement combined filter pack-bitmap: implement object type filter list-objects: implement object type filter list-objects: support filtering by tag and commit list-objects: move tag processing into its own function revision: mark commit parents as NOT_USER_GIVEN uploadpack.txt: document implication of `uploadpackfilter.allow`

Merge branch 'jk/prune-with-bitmap-fix'

2021-05-07T03:47:38Z

When the reachability bitmap is in effect, the "do not lose recently created objects and those that are reachable from them" safety to protect us from races were disabled by mistake, which has been corrected. * jk/prune-with-bitmap-fix: prune: save reachable-from-recent objects with bitmaps pack-bitmap: clean up include_check after use

pack-bitmap: clean up include_check after use

2021-04-29T01:03:46Z

When a bitmap walk has to traverse (to fill in non-bitmapped objects), we use rev_info's include_check mechanism to let us stop the traversal early. But after setting the function and its data parameter, we never clean it up. This means that if the rev_info is used for a subsequent traversal without bitmaps, it will unexpectedly call into our include_check function (worse, it will do so pointing to a now-defunct stack variable in include_check_data, likely resulting in a segfault). There's no code which does this now, but it's an accident waiting to happen. Let's clean up after ourselves in the bitmap code. Reported-by: David Emett Signed-off-by: Jeff King Signed-off-by: Junio C Hamano

rev-list: allow filtering of provided items

2021-04-19T21:09:11Z

When providing an object filter, it is currently impossible to also filter provided items. E.g. when executing `git rev-list HEAD` , the commit this reference points to will be treated as user-provided and is thus excluded from the filtering mechanism. This makes it harder than necessary to properly use the new `--filter=object:type` filter given that even if the user wants to only see blobs, he'll still see commits of provided references. Improve this by introducing a new `--filter-provided-objects` option to the git-rev-parse(1) command. If given, then all user-provided references will be subject to filtering. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

pack-bitmap: implement combined filter

2021-04-19T21:09:11Z

When the user has multiple objects filters specified, then this is internally represented by having a "combined" filter. These combined filters aren't yet supported by bitmap indices and can thus not be accelerated. Fix this by implementing support for these combined filters. The implementation is quite trivial: when there's a combined filter, we simply recurse into `filter_bitmap()` for all of the sub-filters. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano