* [PATCH v3 2/3] daemon: fix IPv6 address truncation in ip2str()
From: Sebastien Tardif via GitGitGadget @ 2026-05-28 2:56 UTC (permalink / raw)
To: git; +Cc: Patrick Steinhardt, Sebastien Tardif, Sebastien Tardif
In-Reply-To: <pull.2300.v3.git.git.1779937016.gitgitgadget@gmail.com>
From: Sebastien Tardif <sebtardif@ncf.ca>
The sockaddr struct size (ai_addrlen) is passed as the output buffer
size to inet_ntop(). For IPv6, sizeof(sockaddr_in6) is 28 bytes but
INET6_ADDRSTRLEN is 46, so long IPv6 addresses are silently truncated.
Fix this by passing sizeof(ip) instead, which is the actual size of
the destination buffer. Drop the now-unused len parameter from
ip2str() and update all callers.
Signed-off-by: Sebastien Tardif <sebtardif@ncf.ca>
---
daemon.c | 14 +++++++-------
1 file changed, 7 insertions(+), 7 deletions(-)
diff --git a/daemon.c b/daemon.c
index 80fa0226d8..103c08d868 100644
--- a/daemon.c
+++ b/daemon.c
@@ -947,7 +947,7 @@ struct socketlist {
size_t alloc;
};
-static const char *ip2str(int family, struct sockaddr *sin, socklen_t len)
+static const char *ip2str(int family, struct sockaddr *sin)
{
#ifdef NO_IPV6
static char ip[INET_ADDRSTRLEN];
@@ -958,11 +958,11 @@ static const char *ip2str(int family, struct sockaddr *sin, socklen_t len)
switch (family) {
#ifndef NO_IPV6
case AF_INET6:
- inet_ntop(family, &((struct sockaddr_in6*)sin)->sin6_addr, ip, len);
+ inet_ntop(family, &((struct sockaddr_in6*)sin)->sin6_addr, ip, sizeof(ip));
break;
#endif
case AF_INET:
- inet_ntop(family, &((struct sockaddr_in*)sin)->sin_addr, ip, len);
+ inet_ntop(family, &((struct sockaddr_in*)sin)->sin_addr, ip, sizeof(ip));
break;
default:
xsnprintf(ip, sizeof(ip), "<unknown>");
@@ -1019,14 +1019,14 @@ static int setup_named_sock(char *listen_addr, int listen_port, struct socketlis
if (bind(sockfd, ai->ai_addr, ai->ai_addrlen) < 0) {
logerror("Could not bind to %s: %s",
- ip2str(ai->ai_family, ai->ai_addr, ai->ai_addrlen),
+ ip2str(ai->ai_family, ai->ai_addr),
strerror(errno));
close(sockfd);
continue; /* not fatal */
}
if (listen(sockfd, 5) < 0) {
logerror("Could not listen to %s: %s",
- ip2str(ai->ai_family, ai->ai_addr, ai->ai_addrlen),
+ ip2str(ai->ai_family, ai->ai_addr),
strerror(errno));
close(sockfd);
continue; /* not fatal */
@@ -1080,7 +1080,7 @@ static int setup_named_sock(char *listen_addr, int listen_port, struct socketlis
if ( bind(sockfd, (struct sockaddr *)&sin, sizeof sin) < 0 ) {
logerror("Could not bind to %s: %s",
- ip2str(AF_INET, (struct sockaddr *)&sin, sizeof(sin)),
+ ip2str(AF_INET, (struct sockaddr *)&sin),
strerror(errno));
close(sockfd);
return 0;
@@ -1088,7 +1088,7 @@ static int setup_named_sock(char *listen_addr, int listen_port, struct socketlis
if (listen(sockfd, 5) < 0) {
logerror("Could not listen to %s: %s",
- ip2str(AF_INET, (struct sockaddr *)&sin, sizeof(sin)),
+ ip2str(AF_INET, (struct sockaddr *)&sin),
strerror(errno));
close(sockfd);
return 0;
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 1/3] daemon: fix IPv6 address corruption in lookup_hostname()
From: Sebastien Tardif via GitGitGadget @ 2026-05-28 2:56 UTC (permalink / raw)
To: git; +Cc: Patrick Steinhardt, Sebastien Tardif, Sebastien Tardif
In-Reply-To: <pull.2300.v3.git.git.1779937016.gitgitgadget@gmail.com>
From: Sebastien Tardif <sebtardif@ncf.ca>
getaddrinfo() is called with AF_UNSPEC hints, so it may return IPv6
results. However, the code unconditionally casts ai_addr to
sockaddr_in and passes AF_INET to inet_ntop(). On IPv6-only hosts,
this reads from the wrong struct offset, producing garbage IP
addresses.
Fix this by checking ai_family and extracting the address pointer
into a local variable before calling inet_ntop() once with the
correct family. Die on unexpected address families.
Signed-off-by: Sebastien Tardif <sebtardif@ncf.ca>
---
daemon.c | 15 +++++++++++++--
1 file changed, 13 insertions(+), 2 deletions(-)
diff --git a/daemon.c b/daemon.c
index 0a7b1aae44..80fa0226d8 100644
--- a/daemon.c
+++ b/daemon.c
@@ -674,9 +674,20 @@ static void lookup_hostname(struct hostinfo *hi)
gai = getaddrinfo(hi->hostname.buf, NULL, &hints, &ai);
if (!gai) {
- struct sockaddr_in *sin_addr = (void *)ai->ai_addr;
+ void *addr;
+
+ if (ai->ai_family == AF_INET) {
+ struct sockaddr_in *sa = (void *)ai->ai_addr;
+ addr = &sa->sin_addr;
+ } else if (ai->ai_family == AF_INET6) {
+ struct sockaddr_in6 *sa6 = (void *)ai->ai_addr;
+ addr = &sa6->sin6_addr;
+ } else {
+ die("unexpected address family: %d",
+ ai->ai_family);
+ }
- inet_ntop(AF_INET, &sin_addr->sin_addr,
+ inet_ntop(ai->ai_family, addr,
addrbuf, sizeof(addrbuf));
strbuf_addstr(&hi->ip_address, addrbuf);
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 0/3] daemon: fix network address handling bugs
From: Sebastien Tardif via GitGitGadget @ 2026-05-28 2:56 UTC (permalink / raw)
To: git; +Cc: Patrick Steinhardt, Sebastien Tardif
In-Reply-To: <pull.2300.v2.git.git.1779905911.gitgitgadget@gmail.com>
Fix three related issues in daemon.c's network address handling:
IPv6 address corruption in lookup_hostname(): getaddrinfo() is called with
AF_UNSPEC hints, so it may return IPv6 results. However, the code
unconditionally casts ai_addr to sockaddr_in and passes AF_INET to
inet_ntop(). On IPv6-only hosts, this reads from the wrong struct offset,
producing garbage IP addresses. Fixed by checking ai_family and handling
both AF_INET and AF_INET6.
IPv6 address truncation in ip2str(): The sockaddr struct size (ai_addrlen)
is passed as the output buffer size to inet_ntop(). For IPv6,
sizeof(sockaddr_in6) is 28 bytes but INET6_ADDRSTRLEN is 46, so long IPv6
addresses are silently truncated. Fixed by passing sizeof(ip) instead, and
dropping the now-unused len parameter.
NULL pointer in execute() logging: REMOTE_PORT environment variable is used
in a format string without a NULL check (only REMOTE_ADDR was checked). If
REMOTE_PORT is unset, NULL is passed to printf's %s, which is undefined
behavior. Fixed by using a fallback string.
Changes since v1:
* Split the single patch into three separate commits, one per fix, per
Patrick's review.
* Deduplicated the address family handling in lookup_hostname(): instead of
duplicating the inet_ntop() call for each family, the address pointer is
extracted into a local void *addr variable first, then inet_ntop() is
called once, per Patrick's suggestion.
* The (void *) intermediate cast on ai_addr is used intentionally: C
guarantees any object pointer round-trips safely through void *, and it
keeps the per-family blocks shorter than spelling out the full struct
casts.
* For the REMOTE_PORT NULL guard: both REMOTE_ADDR and REMOTE_PORT are set
by the same code path in handle(), so neither should be NULL
independently. The guard makes the code consistent with the existing
REMOTE_ADDR check and avoids undefined behavior from printf %s with a
NULL argument.
* Die on unexpected address families in lookup_hostname() rather than
silently leaving addrbuf uninitialized.
Sebastien Tardif (3):
daemon: fix IPv6 address corruption in lookup_hostname()
daemon: fix IPv6 address truncation in ip2str()
daemon: guard NULL REMOTE_PORT in execute() logging
daemon.c | 31 +++++++++++++++++++++----------
1 file changed, 21 insertions(+), 10 deletions(-)
base-commit: 59ff4886a579f4bc91e976fe18590b9ae02c7a08
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2300%2FSebTardif%2Ffix%2Fdaemon-ipv6-and-null-port-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2300/SebTardif/fix/daemon-ipv6-and-null-port-v3
Pull-Request: https://github.com/git/git/pull/2300
Range-diff vs v2:
1: b2d8143811 = 1: b2d8143811 daemon: fix IPv6 address corruption in lookup_hostname()
2: 5c01ec3cad = 2: 5c01ec3cad daemon: fix IPv6 address truncation in ip2str()
3: e312735716 ! 3: 4e74294071 daemon: guard NULL REMOTE_PORT in execute() logging
@@ Commit message
daemon: guard NULL REMOTE_PORT in execute() logging
REMOTE_ADDR and REMOTE_PORT are both set by the same code path in
- handle(), so neither should be NULL independently. However, the
- existing code checks REMOTE_ADDR before the loginfo() call but not
- REMOTE_PORT. If REMOTE_PORT were unset, NULL would be passed to
+ handle(), so when the existing REMOTE_ADDR check passes, REMOTE_PORT
+ is guaranteed to be non-NULL. Guard REMOTE_PORT as well so that a
+ future change that breaks this invariant does not pass NULL to
printf's %s, which is undefined behavior.
- Add a fallback string for the NULL case, matching the existing
- REMOTE_ADDR guard for consistency.
-
Signed-off-by: Sebastien Tardif <sebtardif@ncf.ca>
## daemon.c ##
--
gitgitgadget
^ permalink raw reply
* Re: [PATCH] http: fix memory leak in fetch_and_setup_pack_index()
From: Lorenzo Pegorari @ 2026-05-28 1:22 UTC (permalink / raw)
To: Jeff King; +Cc: git, Taylor Blau, Junio C Hamano, Patrick Steinhardt, fox
In-Reply-To: <20260519191743.GA2269222@coredump.intra.peff.net>
On Tue, May 19, 2026 at 03:17:43PM -0400, Jeff King wrote:
> On Tue, May 19, 2026 at 04:54:45PM +0200, LorenzoPegorari wrote:
>
> > Inside the function `fetch_and_setup_pack_index()`, when the pack
> > obtained using `fetch_pack_index()` fails to be verified by
> > `parse_pack_index()`, the function returns without closing and freeing
> > said pack.
> >
> > Fix this by calling `close_pack_index()` to munmap the index file for
> > the leaking pack (which might have been mmapped by `fetch_pack_index()`
> > or `verify_pack_index()`), and then free it.
>
> OK, I agree we are leaking here, but after reading the patch I'm left
> with a few questions.
>
> > ret = verify_pack_index(new_pack);
> > - if (!ret)
> > - close_pack_index(new_pack);
> > +
> > + close_pack_index(new_pack);
>
> This part was a little confusing at first, because it looked like we are
> already closing the index. But we were doing so on _success_, not on
> failure. Which is a little funny since the point is to be able to read
> from it later, but OK.
>
> At any rate, that is an existing oddity, and I agree that closing it
> before freeing the struct is obviously the right thing to do.
It is indeed weird that we are closing only on success, and not on
failure.
> > free(tmp_idx);
> > - if (ret)
> > + if (ret) {
> > + free(new_pack);
> > return -1;
> > + }
>
> And here we free the actual struct. Good.
>
> But this existing free(tmp_idx) is what puzzles me. We do not need the
> filename anymore regardless of success or failure, so freeing it makes
> sense. But earlier in the function we have:
>
> new_pack = parse_pack_index(the_repository, sha1, tmp_idx);
> if (!new_pack) {
> unlink(tmp_idx);
> free(tmp_idx);
>
> return -1; /* parse_pack_index() already issued error message */
> }
>
> So on parse failure we actually unlink it, but not on verification
> failure. Which seems like it would leave cruft after the process ends.
> And I suspect we probably we did prior to 63aca3f7f1 (dumb-http: store
> downloaded pack idx as tempfile, 2024-10-25), when we started
> registering it as a tempfile to be deleted at process exit.
>
> So I _think_ we could get away with dropping the existing unlink() call
> and just let it get cleaned up at process exit. But if we are going to
> keep it, do we want to also unlink() in this error path? At which point
> it might make more sense to have an "out" label to consolidate all of
> this cleanup.
>
> If we are going to unlink() here it may also make sense to just return
> the tempfile struct from fetch_pack_index(), and then we can call
> delete_tempfile() on it. See the in-code comment in 63aca3f7f1 which
> mentions this hackery.
>
> So I dunno. I think your patch is doing the right thing as-is, but it
> may be worth taking a moment to clean this up a bit further.
The `unlink()` indeed is weird. Pointing me to the commit 63aca3f7f1
really helped me understand how the code changed and the current
situation. Thanks a lot for that.
I've tried testing as thoroughly as possible whether removing the
`unlink()` function call wouldn't change the expected behavior.
*I think* that it can be removed safely, but I'm not 100% sure yet.
If this is the case, I think adding a `goto` "cleanup label" is not
necessary.
> -Peff
Thank you so much Peff for going through this patch,
Lorenzo
^ permalink raw reply
* Re: [PATCH] describe: bail of --contains --all is used with --exclude or --match
From: Jacob Keller @ 2026-05-28 0:43 UTC (permalink / raw)
To: Tuomas Ahola; +Cc: Jacob Keller, git
In-Reply-To: <20260519083559.onq6r%taahol@utu.fi>
On Tue, May 19, 2026 at 1:36 AM Tuomas Ahola <taahol@utu.fi> wrote:
>
> Jacob Keller <jacob.e.keller@intel.com> wrote:
>
> > From: Jacob Keller <jacob.keller@gmail.com>
> >
> > If you try to use git describe --contains with --all, the exclude and
> > match patterns are silently ignored.
> >
> > This results in unexpected behavior, as you may try to provide patterns
> > and expect it to change the result.
> >
>
> I got just bitten by that, and yes, it was quite unexpected.
>
> > Check for this, and have describe die when it encounters this, instead
> > of silently ignoring the provided options.
> >
> > Signed-off-by: Jacob Keller <jacob.keller@gmail.com>
> > ---
> >
> > I just found this while trying to use it, the patterns weren't being applied
> > properly.
> >
> > This is pretty quick/dirty, I haven't had time to write a test, or anything.
> >
>
> Would you like to resurrect the patch? It seems it was never merged,
> nor the underlying problem fixed:
>
> ```
> $ git describe --contains --all --match=bogus
> master
> $ git describe --contains --all --exclude="*"
> master
> ```
>
Apologies for a delayed response. I'll try to look into reviving this tomorrow.
^ permalink raw reply
* Re: git mv after the fact
From: Junio C Hamano @ 2026-05-27 23:22 UTC (permalink / raw)
To: Chris Torek; +Cc: Frieder Hannenheim, git
In-Reply-To: <CAPx1GvetxY1T7cuFN_xe51EURr-ED2BqW3E82jj90ko3PSYSyg@mail.gmail.com>
Chris Torek <chris.torek@gmail.com> writes:
>> Chris Torek <chris.torek@gmail.com> writes:
>>> A flag for "git mv" would be convenient (and slightly moreefficient ...
>>
>
> On Tue, May 26, 2026 at 8:09 PM Junio C Hamano <gitster@pobox.com> wrote:
>> May be convenient, but I do not get the "efficient" part.
>
> A normal `git mv` renames the index entry and the file in the working
> tree without running `git add` on the *contents*, so there's no new hash
> computation. Presumably a `git mv --after foo bar` would do the same: verify
> that there is no existing `bar` in the index, that there is an existing `foo` in
> the index, and that there is no `foo` but there is a `bar` in the working tree,
> and then it would rename (add-and-remove, really, because of sorting)
> the index entry, without scanning the working tree contents.
>
> In other words, we skip reading the 3 terabyte file, or whatever.
Yup, that matches what I wrote. We do not rehash and we only write
the index just once.
> Anyway, comparing to `git rm --cached`:
>
>> I think the requested "feature" is not all that outrageous. It
>> would be a similar value as a morning-after correction measure for
>> "oops, I moved the file in the filesystem without telling Git".
>
> I agree, but I also don't see it as valuable enough to bother
> writing a proper implementation.
Yup, I was merely agreeing with your "convenient" comment. I do not
think it is such a high-priority item for any active developers
among us to drop something they are doing and writing it instead.
^ permalink raw reply
* [PATCH 3/3] pack-objects: support `--delta-islands` with `--path-walk`
From: Taylor Blau @ 2026-05-27 23:18 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Junio C Hamano, Jeff King, Elijah Newren
In-Reply-To: <cover.1779923907.git.me@ttaylorr.com>
Since the inception of `--path-walk`, this option has had a documented
incompatibility with `--delta-islands`.
When discussing those original patches on the list, a message from
Stolee in [1] noted the following:
this could be remedied by [...] doing a separate walk to identify
islands using the normal method
In a related portion of the thread, Peff explains[2]:
The delta islands code already does its own tree walk to propagate
the bits down (it does rely on the base walk's show_commit() to
propagate through the commits).
Once each object has its island bitmaps, I think however you
choose to come up with delta candidates [...] you should be able
to use it. It's fundamentally just answering the question of "am
I allowed to delta between these two objects".
That is similar to what this patch does, and it turns out the cheaper
option is sufficient: perform the same island side effects from the
path-walk callback rather than doing a second walk.
Recall how delta-islands are computed during a normal repack:
- `show_commit()` calls `propagate_island_marks()` for each commit,
which merges the commit's island bitset onto its root tree object and
onto each of its parent commits.
- `show_object()` for a tree records the tree's depth derived from the
slash-separated pathname. Subsequent `resolve_tree_islands()` uses
that depth to walk trees in increasing-depth order, propagating each
tree's marks to its children.
- At delta-search time, `in_same_island()` enforces that a delta
target's island bitmap is a subset of its base's: every island that
reaches the target must also reach the base.
Path-walk's enumeration callback is `add_objects_by_path()`. It already
adds objects to `to_pack`, but until now did not perform the
island-related side effects. Two things are needed:
- For each commit batch, call `propagate_island_marks()` on commits,
exactly as `show_commit()` does.
We have to be careful about the order in which we call this function,
and we must see a commit before its parents in order to have
island marks to propagate.
The path-walk batch preserves that order. Path-walk appends commits
to its `OBJ_COMMIT` batch as they come back from the same
`get_revision()` loop the regular traversal uses, and
`add_objects_by_path()` iterates the batch in array order. So every
commit reaches `propagate_island_marks()` in the same sequence that
`show_commit()` would have seen it, and the descendant-first chain
that the algorithm relies on is intact.
Skip island propagation for excluded commits to match the regular
traversal, whose `show_commit()` callback is only invoked for
interesting commits. Boundary commits may still be present in
path-walk's callback so they can serve as thin-pack bases, but they
should not contribute island marks.
- For each tree batch, record the tree's depth from the path. Use the
`record_tree_depth()` helper from the previous commit so both
callbacks behave identically, including the max-depth-wins behavior
when a tree is reached via more than one path. The helper accepts
both the `show_object()` path shape ("foo", "foo/bar") and the
path-walk shape with a trailing slash ("foo/", "foo/bar/"), so depths
recorded from either traversal mode are directly comparable.
This is implicit in the implementation sketch from Peff above.
`resolve_tree_islands()` sorts trees by `oe->tree_depth` in
increasing-depth order before propagating marks down, so that a
parent tree's marks are finalized before its children inherit them.
Without recording the depth at path-walk time, every
path-walk-discovered tree would land at depth 0 in `to_pack`, the
sort would lose its ordering, and children could inherit marks from
parents whose own contributions had not yet been merged in.
With those two pieces in place, `resolve_tree_islands()` receives the
same island inputs from path-walk as it would from the regular
traversal, so the existing island checks can be reused unchanged.
Drop the documented incompatibility between `--path-walk` and
`--delta-islands`, and add t5320 coverage for path-walk island repacks
with and without bitmap writing, as well as the same-island case where a
delta remains allowed.
[1]: https://lore.kernel.org/git/9aa2471b-0850-4707-9733-d3b33609f5f2@gmail.com/
[2]: https://lore.kernel.org/git/20240911063203.GA1538586@coredump.intra.peff.net/
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
Documentation/git-pack-objects.adoc | 14 +++++++-------
builtin/pack-objects.c | 22 ++++++++++++++++++----
t/t5320-delta-islands.sh | 29 +++++++++++++++++++++++++++++
3 files changed, 54 insertions(+), 11 deletions(-)
diff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc
index 0adce8961a3..65cd00c152f 100644
--- a/Documentation/git-pack-objects.adoc
+++ b/Documentation/git-pack-objects.adoc
@@ -402,13 +402,13 @@ will be automatically changed to version `1`.
of filenames that cause collisions in Git's default name-hash
algorithm.
+
-Incompatible with `--delta-islands`. When `--use-bitmap-index` is
-specified with `--path-walk`, a successful bitmap traversal is used for
-object enumeration, with path-walk remaining as the fallback traversal
-when the bitmap cannot satisfy the request. The `--path-walk` option
-supports the `--filter=<spec>` forms `blob:none`, `blob:limit=<n>`,
-`tree:0`, `object:type=<type>`, and `sparse:<oid>`. These supported filter
-types can be combined with the `combine:<spec>+<spec>` form.
+When `--use-bitmap-index` is specified with `--path-walk`, a successful
+bitmap traversal is used for object enumeration, with path-walk
+remaining as the fallback traversal when the bitmap cannot satisfy the
+request. The `--path-walk` option supports the `--filter=<spec>` forms
+`blob:none`, `blob:limit=<n>`, `tree:0`, `object:type=<type>`, and
+`sparse:<oid>`. These supported filter types can be combined with the
+`combine:<spec>+<spec>` form.
DELTA ISLANDS
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index ec02e2b21d2..f48ea7a888b 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -4737,13 +4737,29 @@ static int add_objects_by_path(const char *path,
add_object_entry(oid, type, path, exclude);
- if (type == OBJ_COMMIT && write_bitmap_index) {
+ if (type == OBJ_COMMIT) {
struct commit *commit;
+ if (!write_bitmap_index && !use_delta_islands)
+ continue;
+
commit = lookup_commit(the_repository, oid);
if (!commit)
die(_("could not find commit %s"), oid_to_hex(oid));
- index_commit_for_bitmap(commit);
+ if (write_bitmap_index)
+ index_commit_for_bitmap(commit);
+ /*
+ * Skip island propagation for boundary commits.
+ * The regular traversal's show_commit() is only
+ * called for interesting commits; matching that
+ * here keeps path-walk from doing extra work that
+ * would only be a no-op anyway (boundary commits
+ * are not in island_marks).
+ */
+ if (use_delta_islands && !exclude)
+ propagate_island_marks(the_repository, commit);
+ } else if (type == OBJ_TREE && use_delta_islands) {
+ record_tree_depth(oid, path);
}
}
@@ -5205,8 +5221,6 @@ int cmd_pack_objects(int argc,
const char *option = NULL;
if (!path_walk_filter_compatible(&filter_options))
option = "--filter";
- else if (use_delta_islands)
- option = "--delta-islands";
if (option) {
warning(_("cannot use %s with %s"),
diff --git a/t/t5320-delta-islands.sh b/t/t5320-delta-islands.sh
index 2c961c70963..9b28344a0a3 100755
--- a/t/t5320-delta-islands.sh
+++ b/t/t5320-delta-islands.sh
@@ -53,6 +53,35 @@ test_expect_success 'separate islands disallows delta' '
! is_delta_base $two $one
'
+test_expect_success 'path-walk island repack respects islands' '
+ GIT_TRACE2_EVENT="$(pwd)/trace.path-walk-islands" \
+ git -c "pack.island=refs/heads/(.*)" repack -adfi \
+ --path-walk 2>err &&
+ test_region pack-objects path-walk trace.path-walk-islands &&
+ test_grep ! "cannot use --delta-islands with --path-walk" err &&
+ ! is_delta_base $one $two &&
+ ! is_delta_base $two $one
+'
+
+test_expect_success 'path-walk island bitmap repack respects islands' '
+ GIT_TRACE2_EVENT="$(pwd)/trace.path-walk-island-bitmap" \
+ git -c "pack.island=refs/heads/(.*)" repack -a -d -f -i -b \
+ --path-walk 2>err &&
+ test_region pack-objects path-walk trace.path-walk-island-bitmap &&
+ test_path_is_file .git/objects/pack/*.bitmap &&
+ git rev-list --test-bitmap --use-bitmap-index one &&
+ test_grep ! "cannot use --delta-islands with --path-walk" err &&
+ ! is_delta_base $one $two &&
+ ! is_delta_base $two $one
+'
+
+test_expect_success 'path-walk same island allows delta' '
+ GIT_TRACE2_EVENT="$(pwd)/trace.path-walk-same-island" \
+ git -c "pack.island=refs/heads" repack -adfi --path-walk &&
+ test_region pack-objects path-walk trace.path-walk-same-island &&
+ is_delta_base $one $two
+'
+
test_expect_success 'same island allows delta' '
git -c "pack.island=refs/heads" repack -adfi &&
is_delta_base $one $two
--
2.54.0.22.ga642305e3c9
^ permalink raw reply related
* [PATCH 2/3] pack-objects: extract `record_tree_depth()` helper
From: Taylor Blau @ 2026-05-27 23:18 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Junio C Hamano, Jeff King, Elijah Newren
In-Reply-To: <cover.1779923907.git.me@ttaylorr.com>
Prepare for a subsequent change that needs to record tree depths from a
second call site by factoring the delta-islands tree-depth bookkeeping
out of `show_object()` and into a helper, `record_tree_depth()`.
The helper looks up the object in `to_pack`, returns early when the
object was not added there, computes the depth from the slash count in
the supplied name, and preserves the existing max-depth-wins behavior
when a tree is reached by more than one path.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
builtin/pack-objects.c | 32 ++++++++++++++++++--------------
1 file changed, 18 insertions(+), 14 deletions(-)
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index e4dcb563b7d..ec02e2b21d2 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2722,6 +2722,22 @@ static inline void oe_set_tree_depth(struct packing_data *pack,
pack->tree_depth[e - pack->objects] = tree_depth;
}
+static void record_tree_depth(const struct object_id *oid, const char *name)
+{
+ const char *p;
+ unsigned depth;
+ struct object_entry *ent;
+
+ /* the empty string is a root tree, which is depth 0 */
+ depth = *name ? 1 : 0;
+ for (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))
+ depth++;
+
+ ent = packlist_find(&to_pack, oid);
+ if (ent && depth > oe_tree_depth(&to_pack, ent))
+ oe_set_tree_depth(&to_pack, ent, depth);
+}
+
/*
* Return the size of the object without doing any delta
* reconstruction (so non-deltas are true object sizes, but deltas
@@ -4375,20 +4391,8 @@ static void show_object(struct object *obj, const char *name,
add_preferred_base_object(name);
add_object_entry(&obj->oid, obj->type, name, 0);
- if (use_delta_islands) {
- const char *p;
- unsigned depth;
- struct object_entry *ent;
-
- /* the empty string is a root tree, which is depth 0 */
- depth = *name ? 1 : 0;
- for (p = strchr(name, '/'); p; p = strchr(p + 1, '/'))
- depth++;
-
- ent = packlist_find(&to_pack, &obj->oid);
- if (ent && depth > oe_tree_depth(&to_pack, ent))
- oe_set_tree_depth(&to_pack, ent, depth);
- }
+ if (use_delta_islands)
+ record_tree_depth(&obj->oid, name);
}
static void show_object__ma_allow_any(struct object *obj, const char *name, void *data)
--
2.54.0.22.ga642305e3c9
^ permalink raw reply related
* [PATCH 1/3] pack-objects: support reachability bitmaps with `--path-walk`
From: Taylor Blau @ 2026-05-27 23:18 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Junio C Hamano, Jeff King, Elijah Newren
In-Reply-To: <cover.1779923907.git.me@ttaylorr.com>
When 'pack-objects' is invoked with '--path-walk', it prevents us from
using reachability bitmaps.
This behavior dates back to 70664d2865c (pack-objects: add --path-walk
option, 2025-05-16), which included a comment in the relevant portion of
the command-line arguments handling that read as follows:
/*
* We must disable the bitmaps because we are removing
* the --objects / --objects-edge[-aggressive] options.
*/
In fb2c309b7d3 (pack-objects: pass --objects with --path-walk,
2026-05-02), path-walk learned to pass '--objects' again, but still
kept bitmap traversal disabled. That leaves two useful cases
unsupported:
* A path-walk repack that writes bitmaps does not give the bitmap
selector any commits, because path-walk reveals commits through
`add_objects_by_path()` rather than through `show_commit()`, where
`index_commit_for_bitmap()` is normally called.
* An invocation like "git pack-objects --use-bitmap-index --path-walk"
never tries an existing bitmap, even when one is available and could
answer the request.
Fortunately for us, neither restriction is required.
* On the writing side: teach the path-walk object callback to call
`index_commit_for_bitmap()` for commits that it adds to the pack.
That gives the bitmap selector the commit candidates it would have
seen from the regular traversal.
* For bitmap reading, keep passing '--objects' to the internal rev_list
machinery, but stop clearing `use_bitmap_index`. If an existing
bitmap can answer the request, use it; otherwise fall back to
path-walk's own enumeration.
There is one wrinkle when it comes to '--boundary', which we must not
pass into the bitmap walk in the presence of both '--path-walk' and
'--use-bitmap-index'. Path-walk needs boundary commits when it performs
its own traversal, in order to discover bases for thin packs, but the
bitmap traversal expects the usual non-boundary state. Work around this
by setting `revs->boundary` as late as possible within
`get_object_list_path_walk()`, after any bitmap attempt has either
succeeded or declined to answer the request.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
Documentation/git-pack-objects.adoc | 6 +++--
builtin/pack-objects.c | 18 +++++++++++++--
t/t5310-pack-bitmaps.sh | 36 +++++++++++++++++++++++++++++
3 files changed, 56 insertions(+), 4 deletions(-)
diff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc
index 8a27aa19fd3..0adce8961a3 100644
--- a/Documentation/git-pack-objects.adoc
+++ b/Documentation/git-pack-objects.adoc
@@ -402,8 +402,10 @@ will be automatically changed to version `1`.
of filenames that cause collisions in Git's default name-hash
algorithm.
+
-Incompatible with `--delta-islands`. The `--use-bitmap-index` option is
-ignored in the presence of `--path-walk`. The `--path-walk` option
+Incompatible with `--delta-islands`. When `--use-bitmap-index` is
+specified with `--path-walk`, a successful bitmap traversal is used for
+object enumeration, with path-walk remaining as the fallback traversal
+when the bitmap cannot satisfy the request. The `--path-walk` option
supports the `--filter=<spec>` forms `blob:none`, `blob:limit=<n>`,
`tree:0`, `object:type=<type>`, and `sparse:<oid>`. These supported filter
types can be combined with the `combine:<spec>+<spec>` form.
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index b783dc62bc9..e4dcb563b7d 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -4732,6 +4732,15 @@ static int add_objects_by_path(const char *path,
continue;
add_object_entry(oid, type, path, exclude);
+
+ if (type == OBJ_COMMIT && write_bitmap_index) {
+ struct commit *commit;
+
+ commit = lookup_commit(the_repository, oid);
+ if (!commit)
+ die(_("could not find commit %s"), oid_to_hex(oid));
+ index_commit_for_bitmap(commit);
+ }
}
oe_end = to_pack.nr_objects;
@@ -4764,6 +4773,13 @@ static int get_object_list_path_walk(struct rev_info *revs)
info.path_fn = add_objects_by_path;
info.path_fn_data = &processed;
+ /*
+ * Path-walk needs boundary commits to discover thin-pack bases, but
+ * bitmap traversal does not understand the boundary state. Set it
+ * here so any prior bitmap attempt sees the usual non-boundary walk.
+ */
+ revs->boundary = 1;
+
/*
* Allow the --[no-]sparse option to be interesting here, if only
* for testing purposes. Paths with no interesting objects will not
@@ -5195,9 +5211,7 @@ int cmd_pack_objects(int argc,
}
}
if (path_walk) {
- strvec_push(&rp, "--boundary");
strvec_push(&rp, "--objects");
- use_bitmap_index = 0;
} else if (thin) {
use_internal_rev_list = 1;
strvec_push(&rp, shallow
diff --git a/t/t5310-pack-bitmaps.sh b/t/t5310-pack-bitmaps.sh
index f693cb56691..69c5da1580a 100755
--- a/t/t5310-pack-bitmaps.sh
+++ b/t/t5310-pack-bitmaps.sh
@@ -577,6 +577,42 @@ test_bitmap_cases
sane_unset GIT_TEST_PACK_USE_BITMAP_BOUNDARY_TRAVERSAL
+test_expect_success 'path-walk repack can write and use bitmap indexes' '
+ test_when_finished "rm -rf path-walk-bitmap" &&
+ git init path-walk-bitmap &&
+ (
+ cd path-walk-bitmap &&
+ test_commit first &&
+ test_commit second &&
+ test_commit third &&
+
+ git repack -a -d -b --path-walk &&
+ git rev-list --test-bitmap --use-bitmap-index HEAD &&
+
+ git rev-parse HEAD >in &&
+
+ git rev-list --objects --no-object-names HEAD >expect.raw &&
+ sort expect.raw >expect &&
+
+ for reuse in true false
+ do
+ : >trace.txt &&
+
+ GIT_TRACE2_EVENT="$(pwd)/trace.txt" \
+ git -c pack.allowPackReuse=$reuse pack-objects \
+ --stdout --revs --path-walk --use-bitmap-index \
+ <in >out.pack &&
+ grep "\"category\":\"bitmap\",\"key\":\"bitmap/hits\"" trace.txt &&
+
+ git index-pack out.pack &&
+
+ list_packed_objects out.idx >actual.raw &&
+ sort actual.raw >actual &&
+ test_cmp expect actual || return 1
+ done
+ )
+'
+
test_expect_success 'incremental repack fails when bitmaps are requested' '
test_commit more-1 &&
test_must_fail git repack -d 2>err &&
--
2.54.0.22.ga642305e3c9
^ permalink raw reply related
* [PATCH 0/3] pack-objects: support bitmaps and delta-islands with `--path-walk`
From: Taylor Blau @ 2026-05-27 23:18 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Junio C Hamano, Jeff King, Elijah Newren
Note to the maintainer:
* This series is based on 'ds/path-walk-filters' with Patrick's
'ps/clang-w-glibc-2.43-and-_Generic' merged in. The former has since
graduated. These are the three remaining patches from my earlier RFC
after Stolee's series incorporated the filter-related pieces.
Here is a trimmed-down reroll of my series to make `--path-walk` work
with reachability bitmaps and delta-islands. This series was originally
an RFC that was a companion to Stolee's recent patches to extend
`--filter` support to `--path-walk` [1].
Since the previous round, Stolee's series has graduated and incorporated
the filter-related patches from my earlier RFC [2]. What remains are the
three patches here that implement support for reachability bitmaps and
delta-islands under `--path-walk`.
* The first patch allows `--path-walk` to use reachability bitmaps when
they can answer the request, falling back to path-walk enumeration
when they cannot. It also lets bitmap writing see the same commit
candidates that the regular traversal would have shown to the bitmap
selector.
* The second patch is preparatory, and factors the
delta-islands-specific tree-depth recording from `show_object()` into
a helper.
* The final patch teaches the path-walk callback to perform the same
delta-islands side effects as the regular traversal: propagating
island marks for commits, and recording tree depths for trees. This
gives `resolve_tree_islands()` the same input in either enumeration
mode, so the existing island checks can be reused unchanged.
Thanks in advance for your review!
[1]: https://lore.kernel.org/git/pull.2101.git.1777731354.gitgitgadget@gmail.com/
[2]: https://lore.kernel.org/git/cover.1777853408.git.me@ttaylorr.com/
Taylor Blau (3):
pack-objects: support reachability bitmaps with `--path-walk`
pack-objects: extract `record_tree_depth()` helper
pack-objects: support `--delta-islands` with `--path-walk`
Documentation/git-pack-objects.adoc | 12 ++---
builtin/pack-objects.c | 68 +++++++++++++++++++++--------
t/t5310-pack-bitmaps.sh | 36 +++++++++++++++
t/t5320-delta-islands.sh | 29 ++++++++++++
4 files changed, 122 insertions(+), 23 deletions(-)
base-commit: 45a9ecee26839cc880fdd5e704339dd3cf4ffc26
--
2.54.0.22.ga642305e3c9
^ permalink raw reply
* Re: [PATCH v2 0/3] daemon: fix network address handling bugs
From: Junio C Hamano @ 2026-05-27 21:00 UTC (permalink / raw)
To: Sebastien Tardif via GitGitGadget
Cc: git, Patrick Steinhardt, Sebastien Tardif
In-Reply-To: <pull.2300.v2.git.git.1779905911.gitgitgadget@gmail.com>
"Sebastien Tardif via GitGitGadget" <gitgitgadget@gmail.com> writes:
> Fix three related issues in daemon.c's network address handling:
>
> IPv6 address corruption in lookup_hostname(): getaddrinfo() is called with
> AF_UNSPEC hints, so it may return IPv6 results. However, the code
> unconditionally casts ai_addr to sockaddr_in and passes AF_INET to
> inet_ntop(). On IPv6-only hosts, this reads from the wrong struct offset,
> producing garbage IP addresses. Fixed by checking ai_family and handling
> both AF_INET and AF_INET6.
>
> IPv6 address truncation in ip2str(): The sockaddr struct size (ai_addrlen)
> is passed as the output buffer size to inet_ntop(). For IPv6,
> sizeof(sockaddr_in6) is 28 bytes but INET6_ADDRSTRLEN is 46, so long IPv6
> addresses are silently truncated. Fixed by passing sizeof(ip) instead, and
> dropping the now-unused len parameter.
>
> NULL pointer in execute() logging: REMOTE_PORT environment variable is used
> in a format string without a NULL check (only REMOTE_ADDR was checked). If
> REMOTE_PORT is unset, NULL is passed to printf's %s, which is undefined
> behavior. Fixed by using a fallback string.
>
> Changes since v1:
>
> * Split the single patch into three separate commits, one per fix, per
> Patrick's review.
This, and all the other items in this list, are differences between
the version before v1 and v2, isn't it? It is OK to pretend that
the pre-v1 version v0 didn't officially exist, but it would be
helpful to see the inter-version improvements for *this* version.
Indeed, range-diff tells us that the commit log improvement is the
only change since the previous iteration.
> Range-diff vs v1:
>
> 1: b2d8143811 = 1: b2d8143811 daemon: fix IPv6 address corruption in lookup_hostname()
> 2: 5c01ec3cad = 2: 5c01ec3cad daemon: fix IPv6 address truncation in ip2str()
> 3: 1b2f9d1a07 ! 3: e312735716 daemon: guard NULL REMOTE_PORT in execute() logging
> @@ Metadata
> ## Commit message ##
> daemon: guard NULL REMOTE_PORT in execute() logging
>
> - The REMOTE_PORT environment variable is used in a format string
> - without a NULL check, while REMOTE_ADDR is checked. If REMOTE_PORT
> - is unset, NULL is passed to printf's %s, which is undefined behavior.
> + REMOTE_ADDR and REMOTE_PORT are both set by the same code path in
> + handle(), so neither should be NULL independently. However, the
> + existing code checks REMOTE_ADDR before the loginfo() call but not
> + REMOTE_PORT. If REMOTE_PORT were unset, NULL would be passed to
> + printf's %s, which is undefined behavior.
This is easier to read than the previous, but it is unclear what the
change is trying to achieve. You first say if addr is set port can
never be unset. So by checking addr before calling loginfo(), the
code effectively is ensuring that addr and port are set.
(1) The word "However" in "However the existing code checks" does
not make much sense to me (I would think "Therefore" is less
confusing, but if what you first said is correct, then it is
quite obvious and can be left unsaid).
(2) It is unclear why "If REMOTE_PORT were unset NULL would be ..."
needs to be brought up. Yes, you are not supposed to pass NULL
to printf that expects "%s" to format it. But isn't the whole
point of checking that addr is not NULL because the caller
knows that loginfo() accesses both, and the caller also knows
that if addr is not NULL, port will never be NULL? Or is this
comment about something other than loginfo() where port is used
without checking neither addr or port? Then it would not make
much sense to bring up "addr is checked before calling
loginfo()".
IOW, the sentence structure got vastly improved than the previous
round, but it made it clearer that what these sentences say is
unclear ;-).
> - Add a fallback string for the NULL case.
> + Add a fallback string for the NULL case, matching the existing
> + REMOTE_ADDR guard for consistency.
I tried to find if there is any existing case (addr ? addr : "") to
match, but I didn't find any. Probably that is because it is not
needed (instead the code does "if (addr) ..." to protect itself).
I think the only valid justification you could give to this change
is to say that even though the current code is perfectly fine as-is
(i.e. as you said, addr and port are both exported at the same time
so it will never happen that addr is non NULL and port is NULL),
somebody who is not so careful can break that arrangement in the
future, and it is a prudent thing to double check that port is not
NULL before using will future-proof this part of the code.
Thanks.
^ permalink raw reply
* Re: [PATCH v2 0/3] line-log: integrate -L with the standard log output pipeline
From: D. Ben Knoble @ 2026-05-27 20:20 UTC (permalink / raw)
To: Michael Montalbo via GitGitGadget; +Cc: git, Michael Montalbo
In-Reply-To: <pull.2094.v2.git.1779738059.gitgitgadget@gmail.com>
On Mon, May 25, 2026 at 3:41 PM Michael Montalbo via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> Since its introduction, git log -L has short-circuited from
> log_tree_commit() into its own output function, bypassing log_tree_diff()
> and log_tree_diff_flush(). This skips no_free save/restore,
> always_show_header, diff_free() cleanup, and means that pickaxe (-S, -G,
> --find-object) and --diff-filter cannot suppress commits whose pairs are all
> filtered out, because show_log() runs before diffcore_std().
>
> This series restructures the flow so that -L goes through the same
> log_tree_diff() -> log_tree_diff_flush() path as normal single-parent and
> merge diffs, then uses that to enable several non-patch diff formats.
>
> Patch 1: revision: move -L setup before output_format-to-diff derivation
>
> Preparatory reorder in setup_revisions(). The -L block sets a default
> DIFF_FORMAT_PATCH when no format is requested; move it before the derivation
> of revs->diff from output_format so the default is visible to that check. No
> behavior change on its own.
>
> Patch 2: line-log: integrate -L output with the standard log-tree pipeline
>
> Rename line_log_print() to line_log_queue_pairs(), stripping it down to only
> queue pre-computed filepairs. log_tree_diff_flush() handles show_log(),
> diffcore_std(), and diff_flush(). This fixes pickaxe and --diff-filter
> suppression, and aligns the commit/diff separator with the rest of log
> output. Rejects --full-diff, which is not yet supported when filepairs are
> pre-computed.
>
> Patch 3: line-log: allow non-patch diff formats with -L
>
> Expand the allowlist to accept --raw, --name-only, --name-status, and
> --summary. These only read filepair metadata already set by the line-log
> machinery. Diff stat formats (--stat, --numstat, --shortstat, --dirstat)
> remain blocked because they call compute_diffstat() on full blob content and
> would show whole-file statistics rather than range-scoped ones.
>
> Changes since v1:
>
> * Patch 2: use !opt->loginfo return convention in log_tree_diff() to match
> the existing single-parent and merge codepaths, instead of returning
> log_tree_diff_flush() directly.
> * Patch 2: reword the early-return removal to explicitly tie it to the
> pipeline change.
> * Patch 2: soften --full-diff rejection to "not yet supported".
> * Patches 2-3: use test_grep consistently in new tests.
> * Patch 2: replace sed | grep pipe with sed > file && test_grep for proper
> exit status handling.
>
> Michael Montalbo (3):
> revision: move -L setup before output_format-to-diff derivation
> line-log: integrate -L output with the standard log-tree pipeline
> line-log: allow non-patch diff formats with -L
>
> Documentation/line-range-options.adoc | 10 +-
> line-log.c | 30 ++----
> line-log.h | 2 +-
> log-tree.c | 10 +-
> revision.c | 24 +++--
> t/t4211-line-log.sh | 100 +++++++++++++++---
> t/t4211/sha1/expect.parallel-change-f-to-main | 1 -
> .../sha256/expect.parallel-change-f-to-main | 1 -
> 8 files changed, 121 insertions(+), 57 deletions(-)
>
>
> base-commit: 9f223ef1c026d91c7ac68cc0211bde255dda6199
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2094%2Fmmontalbo%2Fmm%2Fline-log-use-log-tree-diff-flush-v2
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2094/mmontalbo/mm/line-log-use-log-tree-diff-flush-v2
> Pull-Request: https://github.com/gitgitgadget/git/pull/2094
>
> Range-diff vs v1:
Looks good.
>
> 1: 9633eb62c6 = 1: 9633eb62c6 revision: move -L setup before output_format-to-diff derivation
> 2: 2d9e0ca015 ! 2: 7acfc5376e line-log: integrate -L output with the standard log-tree pipeline
> @@ Commit message
> log_tree_diff_flush(), mirroring the diff_tree_oid() + flush
> pattern used by the single-parent and merge codepaths.
>
> - - Remove the early return in log_tree_commit() that bypassed
> - no_free save/restore, always_show_header, and diff_free().
> + - Remove the early return in log_tree_commit() that is no longer
> + needed now that -L output flows through log_tree_diff() and
> + log_tree_diff_flush(); this restores no_free save/restore,
> + always_show_header, and diff_free() cleanup.
>
> Because show_log() is now deferred until after diffcore_std() inside
> log_tree_diff_flush(), pickaxe (-S, -G, --find-object) and
> @@ Commit message
> log_tree_diff_flush() only emits one for verbose headers. This
> matches the rest of log output.
>
> - Also reject --full-diff, which is meaningless with -L: the filepairs
> - are pre-computed during the history walk and scoped to tracked paths,
> - so there is no tree diff to widen.
> + Also reject --full-diff, which is not yet supported with -L: the
> + filepairs are pre-computed during the history walk and scoped to
> + tracked line ranges, so there is currently no full-tree diff to
> + fall back to for display.
>
> Update tests accordingly.
>
> @@ log-tree.c: static int log_tree_diff(struct rev_info *opt, struct commit *commit
>
> + if (opt->line_level_traverse) {
> + line_log_queue_pairs(opt, commit);
> -+ return log_tree_diff_flush(opt);
> ++ log_tree_diff_flush(opt);
> ++ return !opt->loginfo;
> + }
> +
> parse_commit_or_die(commit);
> @@ log-tree.c: int log_tree_commit(struct rev_info *opt, struct commit *commit)
>
> ## revision.c ##
> @@ revision.c: int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
> + die(_("the option '%s' requires '%s'"), "--grep-reflog", "--walk-reflogs");
> +
> if (revs->line_level_traverse &&
> - (revs->diffopt.output_format & ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT)))
> - die(_("-L does not yet support diff formats besides -p and -s"));
> -+ if (revs->line_level_traverse && revs->full_diff)
> -+ die(_("-L is not compatible with --full-diff"));
> +- (revs->diffopt.output_format & ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT)))
> +- die(_("-L does not yet support diff formats besides -p and -s"));
> ++ (revs->full_diff ||
> ++ (revs->diffopt.output_format &
> ++ ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT))))
> ++ die(_("-L does not yet support the requested diff format"));
>
> if (revs->expand_tabs_in_log < 0)
> revs->expand_tabs_in_log = revs->expand_tabs_in_log_default;
> @@ t/t4211-line-log.sh: test_expect_success '-L with -G filters to diff-text matche
> + test_cmp expect actual
> +'
> +
> -+test_expect_success '--full-diff is not supported with -L' '
> ++test_expect_success '--full-diff is not yet supported with -L' '
> + test_must_fail git log -L1,24:b.c --full-diff 2>err &&
> -+ test_grep "not compatible with --full-diff" err
> ++ test_grep "does not yet support" err
> +'
> +
> +test_expect_success '-L --oneline has no extra blank line before diff' '
> + git checkout parent-oids &&
> + git log --oneline -L:func2:file.c -1 >actual &&
> + # Oneline header on line 1, diff starts immediately on line 2
> -+ sed -n 2p actual | grep "^diff --git"
> ++ sed -n 2p actual >line2 &&
> ++ test_grep "^diff --git" line2
> +'
> +
> test_done
> 3: 06c24b416f ! 3: 10a3d8dde2 line-log: allow non-patch diff formats with -L
> @@ Documentation/line-range-options.adoc
>
> ## revision.c ##
> @@ revision.c: int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
> - die(_("the option '%s' requires '%s'"), "--grep-reflog", "--walk-reflogs");
> -
> if (revs->line_level_traverse &&
> -- (revs->diffopt.output_format & ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT)))
> -- die(_("-L does not yet support diff formats besides -p and -s"));
> -+ (revs->diffopt.output_format &
> -+ ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT |
> -+ DIFF_FORMAT_RAW | DIFF_FORMAT_NAME |
> -+ DIFF_FORMAT_NAME_STATUS | DIFF_FORMAT_SUMMARY)))
> -+ die(_("-L does not yet support the requested diff format"));
> - if (revs->line_level_traverse && revs->full_diff)
> - die(_("-L is not compatible with --full-diff"));
> + (revs->full_diff ||
> + (revs->diffopt.output_format &
> +- ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT))))
> ++ ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT |
> ++ DIFF_FORMAT_RAW | DIFF_FORMAT_NAME |
> ++ DIFF_FORMAT_NAME_STATUS | DIFF_FORMAT_SUMMARY))))
> + die(_("-L does not yet support the requested diff format"));
>
> + if (revs->expand_tabs_in_log < 0)
>
> ## t/t4211-line-log.sh ##
> @@ t/t4211-line-log.sh: test_expect_success '-p shows the default patch output' '
> @@ t/t4211-line-log.sh: test_expect_success '-p shows the default patch output' '
> - test_must_fail git log -L1,24:b.c --raw
> +test_expect_success '--raw shows mode, oid, status and path' '
> + git log -L1,24:b.c --raw --format= >actual &&
> -+ grep "^:100644 100644 [0-9a-f]\{7\} [0-9a-f]\{7\} M b.c$" actual &&
> -+ ! grep "^diff --git" actual &&
> -+ ! grep "^@@" actual
> ++ test_grep "^:100644 100644 [0-9a-f]\{7\} [0-9a-f]\{7\} M b.c$" actual &&
> ++ ! test_grep "^diff --git" actual &&
> ++ ! test_grep "^@@" actual
I wish we had docs for all the little test helpers… in particular, I
think this is supposed to be "test_grep !" ?
> +'
> +
> +test_expect_success '--name-only shows path' '
> + git log -L1,24:b.c --name-only --format= >actual &&
> -+ grep "^b.c$" actual &&
> -+ ! grep "^diff --git" actual &&
> -+ ! grep "^@@" actual
> ++ test_grep "^b.c$" actual &&
> ++ ! test_grep "^diff --git" actual &&
> ++ ! test_grep "^@@" actual
> +'
> +
> +test_expect_success '--name-status shows status and path' '
> + git log -L1,24:b.c --name-status --format= >actual &&
> -+ grep "^M b.c$" actual &&
> -+ ! grep "^diff --git" actual &&
> -+ ! grep "^@@" actual
> ++ test_grep "^M b.c$" actual &&
> ++ ! test_grep "^diff --git" actual &&
> ++ ! test_grep "^@@" actual
> +'
> +
> +test_expect_success '--stat is not yet supported with -L' '
> @@ t/t4211-line-log.sh: test_expect_success '-p shows the default patch output' '
>
> test_expect_success 'setup for checking fancy rename following' '
> @@ t/t4211-line-log.sh: test_expect_success '-L --oneline has no extra blank line before diff' '
> - sed -n 2p actual | grep "^diff --git"
> + test_grep "^diff --git" line2
> '
>
> +test_expect_success '--summary shows new file on root commit' '
> + git checkout parent-oids &&
> + git log -L:func2:file.c --summary --format= >actual &&
> -+ grep "create mode 100644 file.c" actual
> ++ test_grep "create mode 100644 file.c" actual
> +'
> +
> test_done
>
> --
> gitgitgadget
Thanks
--
D. Ben Knoble
^ permalink raw reply
* [PATCH v2 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps
From: Taylor Blau @ 2026-05-27 19:56 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779911733.git.me@ttaylorr.com>
When generating bitmaps, `bitmap_builder_init()` starts with an initial
selection of commits to receive bitmap coverage, and then determines a
set of "maximal" commits based on its input.
Commit 089f751360f (pack-bitmap-write: build fewer intermediate bitmaps,
2020-12-08) has extensive details, but the gist is as follows:
Each selected commit starts with one commit_mask bit in its "commit
mask" bitmap. Then, we walk the first-parent history in topological
order and OR each commit's mask into its (first) parent. Whenever that
OR results in the parent having more bits set, the child is deemed to be
non-maximal, and the frontier is pushed further back along the first
parent history.
That approach works extremely well for ordinary selected commits, whose
first-parent histories often describe real sharing between the bitmaps
we are going to write.
It struggles, however, to efficiently generate pseudo-merge bitmaps.
Unlike ordinary commits for which the above algorithm is designed,
pseudo-merges don't represent any "real" commit in history, just a
grouping of non-bitmapped reference tips. In that sense, their first
parent is just a part of a larger set, and treating them like ordinary
selected commits imposes a significant slow-down when generating bitmaps
with pseudo-merges enabled.
Consider partitioning all non-bitmapped reference tips into eight
individual pseudo-merges via the following configuration:
[bitmapPseudoMerge "all"]
pattern=refs/
threshold=now
stableSize=10000000
maxMerges=8
, the cost of generating a bitmap from scratch rises significantly:
+------------------+-----------------+---------------+---------------------+
| | no pseudo-merge | pseudo-merges | Delta |
| | | (HEAD^) | |
+------------------+-----------------+---------------+---------------------+
| elapsed | 294.1 s | 575.0 s | +280.9 s (+95.5%) |
| cycles | 1,365.5 B | 2,686.9 B | +1,321.4 B (+96.8%) |
| instructions | 1,389.8 B | 2,546.6 B | +1,156.8 B (+83.2%) |
| CPI | 0.983 | 1.055 | +0.073 (+7.4%) |
+------------------+-----------------+---------------+---------------------+
This is a particularly poor trade-off, because the time saved by these
pseudo-merges during, e.g.,
$ git rev-list --count --all --objects --use-bitmap-index
is only:
$ hyperfine -L v true,false -n 'pseudo-merges: {v}' '
GIT_TEST_USE_PSEUDO_MERGES={v} git.compile rev-list --count \
--objects --all --use-bitmap-index
'
Benchmark 1: pseudo-merges: true
Time (mean ± σ): 2.613 s ± 0.012 s [User: 2.308 s, System: 0.305 s]
Range (min … max): 2.594 s … 2.633 s 10 runs
Benchmark 2: pseudo-merges: false
Time (mean ± σ): 52.205 s ± 0.170 s [User: 51.500 s, System: 0.697 s]
Range (min … max): 51.956 s … 52.458 s 10 runs
Summary
pseudo-merges: true ran
19.98 ± 0.11 times faster than pseudo-merges: false
In other words, we pay a nearly ~5 minute penalty to generate
pseudo-merge bitmaps, but only save ~50 seconds during traversal.
The problem stems from injecting pseudo-merges into the bitmap builder
as if they were normal commits. The maximal commit selection algorithm
was simply not designed for that case, and performs predictably poorly.
The only reason we reused the maximal commit selection routine for
pseudo-merges alongside regular non-pseudo-merge commits is because we
represent them both as commit objects (where the pseudo-merge commits
just represent a made-up commit as opposed to one that actually exists
in a repository's object store).
Instead, build the regular selected commit bitmaps first, considering
only non-pseudo-merge commits in `bitmap_builder_init()`. Once those
bitmaps have been stored, build each pseudo-merge bitmap separately and
attach its parent and object bitmaps to the corresponding pseudo-merge
entry before writing the extension.
This keeps the regular bitmap build shaped like the no-pseudo-merge
case. The later pseudo-merge fill can still stop at stored selected
ancestor bitmaps, so it does not have to rewalk each pseudo-merge
closure from scratch.
When an existing bitmap has the same pseudo-merge parent set, reuse and
remap that whole pseudo-merge bitmap before falling back to
fill_bitmap_commit(). This preserves the benefit of stable pseudo-merges
while keeping the on-disk format and reader behavior unchanged.
As a result, the overhead cost for generating pseudo-merges in the above
configuration is much smaller:
+------------------+-----------------+---------------+-------------------+
| | no pseudo-merge | pseudo-merges | Delta |
| | | (HEAD) | |
+------------------+-----------------+---------------+-------------------+
| elapsed | 294.1 s | 328.4 s | +34.3 s (+11.7%) |
| cycles | 1,365.5 B | 1,529.3 B | +163.7 B (+12.0%) |
| instructions | 1,389.8 B | 1,552.8 B | +163.0 B (+11.7%) |
| CPI | 0.983 | 0.985 | +0.002 (+0.2%) |
+------------------+-----------------+---------------+-------------------+
Recall that at the start of this series, generating reachability bitmaps
took 612.5 seconds *without* pseudo-merges. With this commit, it is
still ~46.38% *faster* to generate reachability bitmaps *with*
pseudo-merges than it was to generate bitmaps wihtout them at the
beginning of this series.
The changes to implement this are mostly straightforward. We exclude
pseudo-merge commits from the existing bitmap generation, and walk over
them in a separate pass, by either reusing an existing on-disk
pseudo-merge, or passing the pseudo-merge commit itself back to the
existing routine in `fill_bitmap_commit()`.
(Note that the routine to build pseudo-merge bitmaps is the same both
before and after this change, the difference is only that we do not let
psuedo-merges participate in determining the set of maximal commits.)
The only wrinkle is that `fill_bitmap_commit()` must be taught to not
expect that all tree objects have been parsed, which is the case for any
portion of history reachable by one or more pseudo-merge(s), but not by
any non-pseudo-merge commit selected for bitmapping.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap-write.c | 210 ++++++++++++++++++++++++++++++++++++--------
1 file changed, 174 insertions(+), 36 deletions(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 8200aed6101..1bcb3f98a42 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -446,13 +446,17 @@ static void bitmap_builder_init(struct bitmap_builder *bb,
revs.topo_order = 1;
revs.first_parent_only = 1;
- for (i = 0; i < writer->selected_nr; i++) {
+ for (i = 0; i < bitmap_writer_nr_selected_commits(writer); i++) {
struct bitmapped_commit *bc = &writer->selected[i];
struct bb_commit *ent = bb_data_at(&bb->data, bc->commit);
+ if (bc->pseudo_merge)
+ BUG("unexpected pseudo-merge at %"PRIuMAX,
+ (uintmax_t)i);
+
ent->selected = 1;
ent->maximal = 1;
- ent->pseudo_merge = bc->pseudo_merge;
+ ent->pseudo_merge = 0;
ent->idx = i;
ent->commit_mask = bitmap_new();
@@ -618,6 +622,8 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
static int reused_bitmaps_nr;
static int reused_pseudo_merge_bitmaps_nr;
+static int pseudo_merge_bitmap_nr;
+static int pseudo_merge_bitmap_parents;
static int fill_bitmap_commit_calls_nr;
static int fill_bitmap_commit_found_ancestor_nr;
@@ -631,8 +637,12 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
const uint32_t *mapping)
{
int found;
+ int from_pseudo_merge = commit->object.flags & BITMAP_PSEUDO_MERGE;
uint32_t pos;
+ if (ent->pseudo_merge)
+ BUG("unexpected pseudo-merge commit in fill_bitmap_commit()");
+
fill_bitmap_commit_calls_nr++;
if (!ent->bitmap)
@@ -648,10 +658,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
struct ewah_bitmap *old;
struct bitmap *remapped = bitmap_new();
- if (commit->object.flags & BITMAP_PSEUDO_MERGE)
- old = pseudo_merge_bitmap_for_commit(old_bitmap, c);
- else
- old = bitmap_for_commit(old_bitmap, c);
+ old = bitmap_for_commit(old_bitmap, c);
/*
* If this commit has an old bitmap, then translate that
* bitmap and add its bits to this one. No need to walk
@@ -660,10 +667,7 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
if (old && !rebuild_bitmap(mapping, old, remapped)) {
bitmap_or(ent->bitmap, remapped);
bitmap_free(remapped);
- if (commit->object.flags & BITMAP_PSEUDO_MERGE)
- reused_pseudo_merge_bitmaps_nr++;
- else
- reused_bitmaps_nr++;
+ reused_bitmaps_nr++;
continue;
}
bitmap_free(remapped);
@@ -696,12 +700,32 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
* walk ensures we cover all parents.
*/
if (!(c->object.flags & BITMAP_PSEUDO_MERGE)) {
+ struct tree *tree;
+
+ if (from_pseudo_merge && !c->object.parsed) {
+ /*
+ * Commits reachable from selected
+ * non-pseudo-merges are already parsed
+ * by the regular bitmap build.
+ *
+ * However, pseudo-merge fills can also
+ * reach commits that were not covered
+ * there, so parse any such leftovers
+ * before reading their tree or parents.
+ */
+ if (repo_parse_commit(writer->repo, c))
+ return -1;
+ }
+
pos = find_object_pos(writer, &c->object.oid, &found);
if (!found)
return -1;
bitmap_set(ent->bitmap, pos);
- prio_queue_put(tree_queue,
- repo_get_commit_tree(writer->repo, c));
+
+ tree = repo_get_commit_tree(writer->repo, c);
+ if (!tree)
+ return -1;
+ prio_queue_put(tree_queue, tree);
}
for (p = c->parents; p; p = p->next) {
@@ -738,6 +762,137 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
return 0;
}
+static int reuse_pseudo_merge_bitmap(struct bitmap_index *old_bitmap,
+ const uint32_t *mapping,
+ struct commit *merge,
+ struct ewah_bitmap **out)
+{
+ struct ewah_bitmap *old;
+ struct bitmap *remapped;
+
+ if (!old_bitmap || !mapping)
+ return 0;
+
+ old = pseudo_merge_bitmap_for_commit(old_bitmap, merge);
+ if (!old)
+ return 0;
+
+ remapped = bitmap_new();
+ if (rebuild_bitmap(mapping, old, remapped) < 0) {
+ bitmap_free(remapped);
+ return 0;
+ }
+
+ *out = bitmap_to_ewah(remapped);
+ bitmap_free(remapped);
+ reused_pseudo_merge_bitmaps_nr++;
+ return 1;
+}
+
+static int build_pseudo_merge_bitmap(struct bitmap_writer *writer,
+ struct bitmap_index *old_bitmap,
+ const uint32_t *mapping,
+ struct commit *merge,
+ struct ewah_bitmap **out)
+{
+ struct bb_commit ent = { 0 };
+ struct prio_queue queue = { NULL };
+ struct prio_queue tree_queue = { NULL };
+ unsigned parents = commit_list_count(merge->parents);
+ int ret;
+
+ ent.bitmap = bitmap_new();
+
+ pseudo_merge_bitmap_nr++;
+ pseudo_merge_bitmap_parents += parents;
+
+ if (reuse_pseudo_merge_bitmap(old_bitmap, mapping, merge, out)) {
+ ret = 0;
+ goto done;
+ }
+
+ ret = fill_bitmap_commit(writer, &ent, merge, &queue, &tree_queue,
+ old_bitmap, mapping);
+
+ if (!ret)
+ *out = bitmap_to_ewah(ent.bitmap);
+
+done:
+ bitmap_free(ent.bitmap);
+ clear_prio_queue(&queue);
+ clear_prio_queue(&tree_queue);
+
+ return ret;
+}
+
+static int build_pseudo_merge_bitmaps(struct bitmap_writer *writer,
+ struct bitmap_index *old_bitmap,
+ const uint32_t *mapping,
+ int *nr_stored)
+{
+ size_t i = bitmap_writer_nr_selected_commits(writer);
+ int ret = 0;
+
+ if (!writer->pseudo_merges_nr)
+ return 0;
+
+ trace2_region_enter("pack-bitmap-write", "building_pseudo_merge_bitmaps",
+ writer->repo);
+
+ for (; i < writer->selected_nr; i++) {
+ struct bitmapped_commit *merge = &writer->selected[i];
+ struct commit_list *p;
+ struct bitmap *parents = bitmap_new();
+ struct ewah_bitmap *objects = NULL;
+
+ if (!merge->pseudo_merge)
+ BUG("found non-pseudo merge commit at %"PRIuMAX,
+ (uintmax_t)i);
+
+ for (p = merge->commit->parents; p; p = p->next) {
+ int found;
+ uint32_t pos = find_object_pos(writer,
+ &p->item->object.oid,
+ &found);
+ if (!found) {
+ bitmap_free(parents);
+ ret = -1;
+ goto done;
+ }
+ bitmap_set(parents, pos);
+ }
+
+ merge->pseudo_merge_parents = bitmap_to_ewah(parents);
+ bitmap_free(parents);
+
+ if (build_pseudo_merge_bitmap(writer, old_bitmap, mapping,
+ merge->commit, &objects) < 0) {
+ ret = -1;
+ goto done;
+ }
+ merge->bitmap = objects;
+
+ (*nr_stored)++;
+ display_progress(writer->progress, *nr_stored);
+ }
+
+done:
+ trace2_region_leave("pack-bitmap-write", "building_pseudo_merge_bitmaps",
+ writer->repo);
+
+ trace2_data_intmax("pack-bitmap-write", writer->repo,
+ "pseudo_merge_bitmap_nr",
+ pseudo_merge_bitmap_nr);
+ trace2_data_intmax("pack-bitmap-write", writer->repo,
+ "building_bitmaps_pseudo_merge_reused",
+ reused_pseudo_merge_bitmaps_nr);
+ trace2_data_intmax("pack-bitmap-write", writer->repo,
+ "pseudo_merge_bitmap_parents",
+ pseudo_merge_bitmap_parents);
+
+ return ret;
+}
+
static void store_selected(struct bitmap_writer *writer,
struct bb_commit *ent, struct commit *commit)
{
@@ -821,6 +976,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)
bitmap_free(ent->bitmap);
ent->bitmap = NULL;
}
+ if (closed &&
+ build_pseudo_merge_bitmaps(writer, old_bitmap, mapping,
+ &nr_stored) < 0)
+ closed = 0;
clear_prio_queue(&queue);
clear_prio_queue(&tree_queue);
bitmap_builder_clear(&bb);
@@ -831,9 +990,6 @@ int bitmap_writer_build(struct bitmap_writer *writer)
writer->repo);
trace2_data_intmax("pack-bitmap-write", writer->repo,
"building_bitmaps_reused", reused_bitmaps_nr);
- trace2_data_intmax("pack-bitmap-write", writer->repo,
- "building_bitmaps_pseudo_merge_reused",
- reused_pseudo_merge_bitmaps_nr);
trace2_data_intmax("pack-bitmap-write", writer->repo,
"fill_bitmap_commit_calls_nr",
fill_bitmap_commit_calls_nr);
@@ -1015,23 +1171,6 @@ static void write_pseudo_merges(struct bitmap_writer *writer,
CALLOC_ARRAY(pseudo_merge_ofs, writer->pseudo_merges_nr);
- for (i = 0; i < writer->pseudo_merges_nr; i++) {
- struct bitmapped_commit *merge = &writer->selected[base + i];
- struct commit_list *p;
- struct bitmap *parents = bitmap_new();
-
- if (!merge->pseudo_merge)
- BUG("found non-pseudo merge commit at %"PRIuMAX, (uintmax_t)i);
-
- for (p = merge->commit->parents; p; p = p->next)
- bitmap_set(parents,
- find_object_pos(writer, &p->item->object.oid,
- NULL));
-
- merge->pseudo_merge_parents = bitmap_to_ewah(parents);
- bitmap_free(parents);
- }
-
start = hashfile_total(f);
for (i = 0; i < writer->pseudo_merges_nr; i++) {
@@ -1040,14 +1179,13 @@ static void write_pseudo_merges(struct bitmap_writer *writer,
if (!merge->pseudo_merge)
BUG("found non-pseudo merge commit at %"PRIuMAX, (uintmax_t)i);
- if (!merge->pseudo_merge_parents)
- BUG("missing pseudo-merge parents bitmap for commit %s",
+ if (!merge->pseudo_merge_parents || !merge->bitmap)
+ BUG("missing pseudo-merge bitmap for commit %s",
oid_to_hex(&merge->commit->object.oid));
pseudo_merge_ofs[i] = hashfile_total(f);
-
dump_bitmap(f, merge->pseudo_merge_parents);
- dump_bitmap(f, writer->selected[base+i].write_as);
+ dump_bitmap(f, merge->bitmap);
}
next_ext = st_add(hashfile_total(f),
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply related
* [PATCH v2 7/8] pack-bitmap: remember pseudo-merge parents
From: Taylor Blau @ 2026-05-27 19:56 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779911733.git.me@ttaylorr.com>
write_pseudo_merges() currently builds an array of temporary bitmaps for
the parent set of each pseudo-merge, then serializes those bitmaps later
while writing the extension.
Move those parent bitmaps onto the corresponding bitmapped_commit
entries instead. This keeps the on-disk output unchanged, but gives the
parent bitmap the same lifetime and access pattern that later changes
will use when pseudo-merge object bitmaps are built before the write
step.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap-write.c | 30 +++++++++++++++++-------------
1 file changed, 17 insertions(+), 13 deletions(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 66282ea14b5..8200aed6101 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -32,6 +32,7 @@ struct bitmapped_commit {
struct commit *commit;
struct ewah_bitmap *bitmap;
struct ewah_bitmap *write_as;
+ struct ewah_bitmap *pseudo_merge_parents;
int flags;
int xor_offset;
uint32_t commit_pos;
@@ -102,6 +103,7 @@ void bitmap_writer_free(struct bitmap_writer *writer)
if (bc->write_as != bc->bitmap)
ewah_free(bc->write_as);
ewah_free(bc->bitmap);
+ ewah_free(bc->pseudo_merge_parents);
}
free(writer->selected);
}
@@ -210,6 +212,7 @@ void bitmap_writer_push_commit(struct bitmap_writer *writer,
writer->selected[writer->selected_nr].write_as = NULL;
writer->selected[writer->selected_nr].flags = 0;
writer->selected[writer->selected_nr].pseudo_merge = pseudo_merge;
+ writer->selected[writer->selected_nr].pseudo_merge_parents = NULL;
writer->selected_nr++;
}
@@ -1004,42 +1007,47 @@ static void write_pseudo_merges(struct bitmap_writer *writer,
struct hashfile *f)
{
struct oid_array commits = OID_ARRAY_INIT;
- struct bitmap **commits_bitmap = NULL;
off_t *pseudo_merge_ofs = NULL;
off_t start, table_start, next_ext;
uint32_t base = bitmap_writer_nr_selected_commits(writer);
size_t i, j = 0;
- CALLOC_ARRAY(commits_bitmap, writer->pseudo_merges_nr);
CALLOC_ARRAY(pseudo_merge_ofs, writer->pseudo_merges_nr);
for (i = 0; i < writer->pseudo_merges_nr; i++) {
struct bitmapped_commit *merge = &writer->selected[base + i];
struct commit_list *p;
+ struct bitmap *parents = bitmap_new();
if (!merge->pseudo_merge)
BUG("found non-pseudo merge commit at %"PRIuMAX, (uintmax_t)i);
- commits_bitmap[i] = bitmap_new();
-
for (p = merge->commit->parents; p; p = p->next)
- bitmap_set(commits_bitmap[i],
+ bitmap_set(parents,
find_object_pos(writer, &p->item->object.oid,
NULL));
+
+ merge->pseudo_merge_parents = bitmap_to_ewah(parents);
+ bitmap_free(parents);
}
start = hashfile_total(f);
for (i = 0; i < writer->pseudo_merges_nr; i++) {
- struct ewah_bitmap *commits_ewah = bitmap_to_ewah(commits_bitmap[i]);
+ struct bitmapped_commit *merge = &writer->selected[base + i];
+
+ if (!merge->pseudo_merge)
+ BUG("found non-pseudo merge commit at %"PRIuMAX, (uintmax_t)i);
+
+ if (!merge->pseudo_merge_parents)
+ BUG("missing pseudo-merge parents bitmap for commit %s",
+ oid_to_hex(&merge->commit->object.oid));
pseudo_merge_ofs[i] = hashfile_total(f);
- dump_bitmap(f, commits_ewah);
+ dump_bitmap(f, merge->pseudo_merge_parents);
dump_bitmap(f, writer->selected[base+i].write_as);
-
- ewah_free(commits_ewah);
}
next_ext = st_add(hashfile_total(f),
@@ -1122,12 +1130,8 @@ static void write_pseudo_merges(struct bitmap_writer *writer,
hashwrite_be64(f, table_start - start);
hashwrite_be64(f, hashfile_total(f) - start + sizeof(uint64_t));
- for (i = 0; i < writer->pseudo_merges_nr; i++)
- bitmap_free(commits_bitmap[i]);
-
oid_array_clear(&commits);
free(pseudo_merge_ofs);
- free(commits_bitmap);
}
static int table_cmp(const void *_va, const void *_vb, void *_data)
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply related
* [PATCH v2 6/8] pack-bitmap: sort bitmaps before XORing
From: Taylor Blau @ 2026-05-27 19:56 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779911733.git.me@ttaylorr.com>
Reachability bitmaps may be stored as XORs against nearby bitmaps, up to
10 away. However, when callers provide selected commits in an arbitrary
order, the writer may miss good ancestor/descendant pairs and produce
much larger bitmap files without changing query coverage.
Sort the selected bitmaps in date order (from oldest to newest) before
computing XOR offsets, leaving pseudo-merge bitmaps alone (which we will
deal with separately in following commits).
On our same testing repository from previous commits, this change shrunk
our selection of 1,261 bitmaps from ~635.46 MiB to 176.4 MiB for a
~72.24% reduction in the on-disk size of our *.bitmap file. The time to
generate the smaller bitmap file decreased by ~3.69 seconds, though this
is likely mostly noise.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap-write.c | 29 +++++++++++++++++++++++++++++
1 file changed, 29 insertions(+)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 4b6fb07edd7..66282ea14b5 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -327,11 +327,40 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,
return 0;
}
+static int bitmapped_commit_date_cmp(const void *_a, const void *_b)
+{
+ const struct bitmapped_commit *a = _a;
+ const struct bitmapped_commit *b = _b;
+
+ if (a->commit->date < b->commit->date)
+ return -1;
+ if (a->commit->date > b->commit->date)
+ return 1;
+ return 0;
+}
+
static void compute_xor_offsets(struct bitmap_writer *writer)
{
static const int MAX_XOR_OFFSET_SEARCH = 10;
int i, next = 0;
+ int nr = bitmap_writer_nr_selected_commits(writer);
+
+ if (nr > 1) {
+ QSORT(writer->selected, nr, bitmapped_commit_date_cmp);
+
+ for (i = 0; i < nr; i++) {
+ struct bitmapped_commit *stored = &writer->selected[i];
+ khiter_t hash_pos = kh_get_oid_map(writer->bitmaps,
+ stored->commit->object.oid);
+
+ if (hash_pos == kh_end(writer->bitmaps))
+ BUG("selected commit missing from bitmap map: %s",
+ oid_to_hex(&stored->commit->object.oid));
+
+ kh_value(writer->bitmaps, hash_pos) = stored;
+ }
+ }
while (next < writer->selected_nr) {
struct bitmapped_commit *stored = &writer->selected[next];
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply related
* [PATCH v2 5/8] pack-bitmap: cache object positions during fill
From: Taylor Blau @ 2026-05-27 19:56 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779911733.git.me@ttaylorr.com>
The previous commits removed some redundant work from bitmap generation
by avoiding unnecessary tree recursion and by reusing selected bitmaps
that have already been computed.
Even with those changes in place, there is still an extremely hot path
from `fill_bitmap_commit()` and `fill_bitmap_tree()` to translate object
IDs into their corresponding bit positions in order to generate their
bitmaps.
In a small repository, this overhead is not significant. However, in a
very large repository (e.g., the one that we have been using as a
benchmark over the past several commits with ~57M total objects), the
overhead of locating object bit positions (often repeatedly) adds up
significantly.
Combat this by adding a small, direct-mapped cache to the bitmap writer
which maps object IDs to their corresponding bit positions. Size the
cache according to the number of objects being written, with fixed lower
and upper bounds so small repositories do not pay for a large table and
large repositories can avoid most repeated packlist and MIDX lookups.
On my machine with (a somewhat outdated) GCC 15.2.0, each entry in the
cache is 40 bytes wide:
$ pahole -C bitmap_pos_cache_entry pack-bitmap-write.o
struct bitmap_pos_cache_entry {
struct object_id oid; /* 0 36 */
uint32_t pos; /* 36 4 */
/* size: 40, cachelines: 1, members: 2 */
/* last cacheline: 40 bytes */
};
, and we will allocate up to 2^21 entries for a maximum total of 80 MiB
of cache overhead.
In our example repository from above and in earlier commits, this
results in a ~9.4% reduction in runtime relative to the previous commit:
+------------------+-------------+-------------+---------------------+
| | HEAD^ | HEAD | Delta |
+------------------+-------------+-------------+---------------------+
| elapsed | 324.8 s | 294.1 s | -30.7 s (-9.4%) |
| cycles | 1,508.6 B | 1,365.5 B | -143.0 B (-9.5%) |
| instructions | 1,436.6 B | 1,389.8 B | -46.9 B (-3.3%) |
| CPI | 1.050 | 0.983 | -0.068 (-6.4%) |
+------------------+-------------+-------------+---------------------+
When generating bitmaps on this repository (to produce the above
timings), the cache grew to its maximum size of 80 MiB, and resulted in
1.024B cache hits and 59.957M cache misses.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap-write.c | 88 ++++++++++++++++++++++++++++++++++++++++++++-
pack-bitmap.h | 7 ++++
2 files changed, 94 insertions(+), 1 deletion(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 42ed22feacc..4b6fb07edd7 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -89,6 +89,7 @@ void bitmap_writer_free(struct bitmap_writer *writer)
ewah_free(writer->tags);
kh_destroy_oid_map(writer->bitmaps);
+ free(writer->pos_cache);
kh_foreach_value(writer->pseudo_merge_commits, idx,
free_pseudo_merge_commit_idx(idx));
@@ -213,15 +214,92 @@ void bitmap_writer_push_commit(struct bitmap_writer *writer,
writer->selected_nr++;
}
+struct bitmap_pos_cache_entry {
+ struct object_id oid;
+ uint32_t pos;
+};
+
+#define BITMAP_POS_MIN_CACHE_SIZE (1U << 10)
+#define BITMAP_POS_MAX_CACHE_SIZE (1U << 21)
+#define BITMAP_POS_CACHE_VALID (1U << 31)
+
+static void bitmap_writer_init_pos_cache(struct bitmap_writer *writer)
+{
+ if (writer->pos_cache)
+ return;
+
+ writer->pos_cache_nr = BITMAP_POS_MIN_CACHE_SIZE;
+
+ while (writer->pos_cache_nr < writer->to_pack->nr_objects &&
+ writer->pos_cache_nr < BITMAP_POS_MAX_CACHE_SIZE)
+ writer->pos_cache_nr <<= 1;
+
+ CALLOC_ARRAY(writer->pos_cache, writer->pos_cache_nr);
+}
+
+static size_t bitmap_writer_pos_cache_slot(struct bitmap_writer *writer,
+ const struct object_id *oid)
+{
+ return oidhash(oid) & (writer->pos_cache_nr - 1);
+}
+
+static bool bitmap_writer_pos_cache_valid(struct bitmap_writer *writer,
+ size_t slot)
+{
+ return !!(writer->pos_cache[slot].pos & BITMAP_POS_CACHE_VALID);
+}
+
+static int find_cached_object_pos(struct bitmap_writer *writer,
+ const struct object_id *oid, uint32_t *pos)
+{
+ size_t slot = bitmap_writer_pos_cache_slot(writer, oid);
+
+ if (bitmap_writer_pos_cache_valid(writer, slot) &&
+ oideq(&writer->pos_cache[slot].oid, oid)) {
+ writer->pos_cache_hits++;
+ *pos = writer->pos_cache[slot].pos & ~BITMAP_POS_CACHE_VALID;
+ return 1;
+ }
+
+ writer->pos_cache_misses++;
+ return 0;
+}
+
+static uint32_t store_cached_object_pos(struct bitmap_writer *writer,
+ const struct object_id *oid,
+ uint32_t pos)
+{
+ size_t slot;
+
+ if (pos & BITMAP_POS_CACHE_VALID)
+ return pos; /* too large to cache */
+
+ slot = bitmap_writer_pos_cache_slot(writer, oid);
+
+ oidcpy(&writer->pos_cache[slot].oid, oid);
+ writer->pos_cache[slot].pos = pos | BITMAP_POS_CACHE_VALID;
+
+ return pos;
+}
+
static uint32_t find_object_pos(struct bitmap_writer *writer,
const struct object_id *oid, int *found)
{
struct object_entry *entry;
uint32_t pos;
+ bitmap_writer_init_pos_cache(writer);
+
+ if (find_cached_object_pos(writer, oid, &pos)) {
+ if (found)
+ *found = 1;
+ return pos;
+ }
+
entry = packlist_find(writer->to_pack, oid);
if (entry) {
uint32_t base_objects = 0;
+
if (writer->midx)
base_objects = writer->midx->num_objects +
writer->midx->num_objects_in_base;
@@ -239,7 +317,7 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,
if (found)
*found = 1;
- return pos;
+ return store_cached_object_pos(writer, oid, pos);
missing:
if (found)
@@ -662,6 +740,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)
writer->progress = start_progress(writer->repo,
"Building bitmaps",
writer->selected_nr);
+
+ writer->pos_cache_hits = 0;
+ writer->pos_cache_misses = 0;
+
trace2_region_enter("pack-bitmap-write", "building_bitmaps_total",
writer->repo);
@@ -726,6 +808,10 @@ int bitmap_writer_build(struct bitmap_writer *writer)
trace2_data_intmax("pack-bitmap-write", writer->repo,
"fill_bitmap_commit_found_ancestor_nr",
fill_bitmap_commit_found_ancestor_nr);
+ trace2_data_intmax("pack-bitmap-write", writer->repo,
+ "bitmap_pos_cache_hits", writer->pos_cache_hits);
+ trace2_data_intmax("pack-bitmap-write", writer->repo,
+ "bitmap_pos_cache_misses", writer->pos_cache_misses);
stop_progress(&writer->progress);
diff --git a/pack-bitmap.h b/pack-bitmap.h
index a95e1c2d115..19a86554579 100644
--- a/pack-bitmap.h
+++ b/pack-bitmap.h
@@ -132,6 +132,8 @@ int bitmap_has_oid_in_uninteresting(struct bitmap_index *, const struct object_i
off_t get_disk_usage_from_bitmap(struct bitmap_index *, struct rev_info *);
+struct bitmap_pos_cache_entry;
+
struct bitmap_writer {
struct repository *repo;
struct ewah_bitmap *commits;
@@ -143,6 +145,11 @@ struct bitmap_writer {
struct packing_data *to_pack;
struct multi_pack_index *midx; /* if appending to a MIDX chain */
+ struct bitmap_pos_cache_entry *pos_cache;
+ size_t pos_cache_nr;
+ uint64_t pos_cache_hits;
+ uint64_t pos_cache_misses;
+
struct bitmapped_commit *selected;
unsigned int selected_nr, selected_alloc;
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply related
* [PATCH v2 4/8] pack-bitmap: consolidate `find_object_pos()` success path
From: Taylor Blau @ 2026-05-27 19:55 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779911733.git.me@ttaylorr.com>
Both sides of `find_object_pos()` report success in the same way by
setting the optional `found` out-parameter and return the resolved
bitmap position.
Prepare for adding more bookkeeping around object-position lookups by
storing the result in a local `pos` variable and sharing the success
return path between the packlist and MIDX cases.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap-write.c | 18 +++++++++---------
1 file changed, 9 insertions(+), 9 deletions(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 651ad467469..42ed22feacc 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -217,6 +217,7 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,
const struct object_id *oid, int *found)
{
struct object_entry *entry;
+ uint32_t pos;
entry = packlist_find(writer->to_pack, oid);
if (entry) {
@@ -224,23 +225,22 @@ static uint32_t find_object_pos(struct bitmap_writer *writer,
if (writer->midx)
base_objects = writer->midx->num_objects +
writer->midx->num_objects_in_base;
-
- if (found)
- *found = 1;
- return oe_in_pack_pos(writer->to_pack, entry) + base_objects;
+ pos = oe_in_pack_pos(writer->to_pack, entry) + base_objects;
} else if (writer->midx) {
- uint32_t at, pos;
+ uint32_t at;
if (!bsearch_midx(oid, writer->midx, &at))
goto missing;
if (midx_to_pack_pos(writer->midx, at, &pos) < 0)
goto missing;
-
- if (found)
- *found = 1;
- return pos;
+ } else {
+ goto missing;
}
+ if (found)
+ *found = 1;
+ return pos;
+
missing:
if (found)
*found = 0;
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply related
* [PATCH v2 3/8] pack-bitmap: reuse stored selected bitmaps
From: Taylor Blau @ 2026-05-27 19:55 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779911733.git.me@ttaylorr.com>
When `fill_bitmap_commit()` reaches an ancestor that was selected for
its own bitmap and processed earlier, its object closure is already
stored in `writer->bitmaps` as an EWAH bitmap. As a result, walking
through that commit's tree and parents again is redundant.
Teach `fill_bitmap_commit()` to notice that case. For non-root commits in
the walk, look for a stored selected bitmap and OR it into the bitmap
being built. If one exists, skip the commit, its tree, and its parents.
Building bitmaps from scratch on the same test repository from the
previous commits yields a significant speed-up:
+------------------+-------------+-------------+---------------------+
| | HEAD^ | HEAD | Delta |
+------------------+-------------+-------------+---------------------+
| elapsed | 562.8 s | 324.8 s | -237.9 s (-42.3%) |
| cycles | 2,621.3 B | 1,508.6 B | -1,112.7 B (-42.4%) |
| instructions | 2,348.9 B | 1,436.6 B | -912.3 B (-38.8%) |
| CPI | 1.116 | 1.050 | -0.066 (-5.9%) |
+------------------+-------------+-------------+---------------------+
In our testing repository, there are 1,261 commits selected for bitmap
coverage, and 1,382 maximal commits induced as a result of that. Of the
1,382 calls made to `fill_bitmap_commit()` (one per maximal commit), 131
of them can be short-circuited at some point during their traversal as a
consequence of this change.
In large repositories where the cost of filling the bitmap for any
individual commit is large, being able to short-circuit even ~9.5% of
the calls to `fill_bitmap_commit()` results in a significant savings.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap-write.c | 34 ++++++++++++++++++++++++++++++++++
1 file changed, 34 insertions(+)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 72610397020..651ad467469 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -509,6 +509,9 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
static int reused_bitmaps_nr;
static int reused_pseudo_merge_bitmaps_nr;
+static int fill_bitmap_commit_calls_nr;
+static int fill_bitmap_commit_found_ancestor_nr;
+
static int fill_bitmap_commit(struct bitmap_writer *writer,
struct bb_commit *ent,
struct commit *commit,
@@ -519,6 +522,9 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
{
int found;
uint32_t pos;
+
+ fill_bitmap_commit_calls_nr++;
+
if (!ent->bitmap)
ent->bitmap = bitmap_new();
@@ -553,6 +559,28 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
bitmap_free(remapped);
}
+ /*
+ * If we encounter an ancestor for which we have already
+ * computed a bitmap during this build (i.e. a regular
+ * selected commit processed earlier in topo order), we can
+ * short-circuit the walk: its stored bitmap already covers
+ * the commit itself, its tree, and all of its ancestors.
+ */
+ if (c != commit) {
+ khiter_t hash_pos = kh_get_oid_map(writer->bitmaps,
+ c->object.oid);
+ if (hash_pos != kh_end(writer->bitmaps)) {
+ struct bitmapped_commit *stored =
+ kh_value(writer->bitmaps, hash_pos);
+ if (stored && stored->bitmap) {
+ fill_bitmap_commit_found_ancestor_nr++;
+ bitmap_or_ewah(ent->bitmap,
+ stored->bitmap);
+ continue;
+ }
+ }
+ }
+
/*
* Mark ourselves and queue our tree. The commit
* walk ensures we cover all parents.
@@ -692,6 +720,12 @@ int bitmap_writer_build(struct bitmap_writer *writer)
trace2_data_intmax("pack-bitmap-write", writer->repo,
"building_bitmaps_pseudo_merge_reused",
reused_pseudo_merge_bitmaps_nr);
+ trace2_data_intmax("pack-bitmap-write", writer->repo,
+ "fill_bitmap_commit_calls_nr",
+ fill_bitmap_commit_calls_nr);
+ trace2_data_intmax("pack-bitmap-write", writer->repo,
+ "fill_bitmap_commit_found_ancestor_nr",
+ fill_bitmap_commit_found_ancestor_nr);
stop_progress(&writer->progress);
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply related
* [PATCH v2 2/8] pack-bitmap: check subtree bits before recursing
From: Taylor Blau @ 2026-05-27 19:55 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779911733.git.me@ttaylorr.com>
In the previous commit, we adjusted the callers of `fill_bitmap_tree()`
to pass in the bit position of the tree they wish to fill.
This commit makes use of that information at the call site to avoid
setting up a stack frame for fill_bitmap_tree() entirely whenever a
tree's bit position is already set.
Since this is such a hot path, the avoided cost of setting up and
tearing down stack frames for each noop'd call to `fill_bitmap_tree()`
is significant:
+--------------+-------------+-------------+-------------------+
| | HEAD^ | HEAD | Delta |
+--------------+-------------+-------------+-------------------+
| elapsed | 582.4 s | 562.8 s | -19.6 s (-3.4%) |
| cycles | 2,713.3 B | 2,621.3 B | -92.0 B (-3.4%) |
| instructions | 2,415.5 B | 2,348.9 B | -66.6 B (-2.8%) |
| CPI | 1.123 | 1.116 | -0.007 (-0.7%) |
+--------------+-------------+-------------+-------------------+
In the same repository as in the previous commit, our timings dropped
from ~582.4 seconds down to ~562.77 seconds.
While the cycles-per-instruction ratio is basically unchanged, we
execute significantly fewer instructions, and correspondingly fewer
cycles.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap-write.c | 23 +++++++++++++++++------
1 file changed, 17 insertions(+), 6 deletions(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 2d5ff8fd406..72610397020 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -463,12 +463,6 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
struct tree_desc desc;
struct name_entry entry;
- /*
- * If our bit is already set, then there is nothing to do. Both this
- * tree and all of its children will be set.
- */
- if (bitmap_get(bitmap, pos))
- return 0;
bitmap_set(bitmap, pos);
if (repo_parse_tree(writer->repo, tree) < 0)
@@ -482,6 +476,15 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
pos = find_object_pos(writer, &entry.oid, &found);
if (!found)
return -1;
+ if (bitmap_get(bitmap, pos)) {
+ /*
+ * If our bit is already set, then there
+ * is nothing to do. Both this tree and
+ * all of its children will be set.
+ */
+ break;
+ }
+
if (fill_bitmap_tree(writer, bitmap,
lookup_tree(writer->repo,
&entry.oid), pos) < 0)
@@ -582,6 +585,14 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
pos = find_object_pos(writer, &t->object.oid, &found);
if (!found)
return -1;
+ if (bitmap_get(ent->bitmap, pos)) {
+ /*
+ * If our bit is already set, then there is
+ * nothing to do. Both this tree and all of its
+ * children will be set.
+ */
+ continue;
+ }
if (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0)
return -1;
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply related
* [PATCH v2 1/8] pack-bitmap: pass object position to `fill_bitmap_tree()`
From: Taylor Blau @ 2026-05-27 19:55 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779911733.git.me@ttaylorr.com>
In the following commit, callers of `fill_bitmap_tree()` will be
required to check the bit corresponding to their tree before calling
that function. That change will reduce the overhead of setting up and
tearing down stack frames for trees whose bits are already set.
To prepare for that change, have callers pass in the tree's bit position
in `fill_bitmap_tree()`, which will make the next commit easier to read.
In the meantime, this change has a surprising and measurable benefit
during bitmap generation, particularly on very large repositories.
When processing sub-trees within `fill_bitmap_tree()`, the preimage of
this patch did the following:
while (tree_entry(&desc, entry)) {
switch (object_type(entry.mode)) {
case OBJ_TREE:
if (fill_bitmap_tree(writer, bitmap,
lookup_tree(writer->repo,
&entry.oid)) < 0) {
/* ... */
}
/* ... */
}
}
, first performing the object lookup via `lookup_tree()`, and then
locating its bit position within the recursive call. This patch
effectively reorders those two calls so that we first discover the
sub-tree's bit position, *then* load its tree.
By reordering these two operations, we spend fewer CPU cycles per
instruction, likely due to improved CPU dependency/cache/pipeline
behavior. Comparing the results of: running `perf stat` before and after
this commit, we have:
+--------------+-------------+-------------+-------------------+
| | HEAD^ | HEAD | Delta |
+--------------+-------------+-------------+-------------------+
| elapsed | 612.5 s | 582.4 s | -30.1 s (-4.9%) |
| cycles | 2,857.3 B | 2,713.3 B | -144.0 B (-5.0%) |
| instructions | 2,413.2 B | 2,415.5 B | +2.3 B (+0.1%) |
| CPI | 1.184 | 1.123 | -0.061 (-5.1%) |
+--------------+-------------+-------------+-------------------+
In a large repository with ~4.8M commit, and ~37.1M tree objects this
change improves timing from ~612.5 seconds down to ~582.4 seconds, or a
~4.9% improvement. More importantly, the number of CPU cycles spent
dropped off significantly as a result of this commit, lowering our
cycles-per-instruction ratio by about ~5.1%.
Signed-off-by: Taylor Blau <me@ttaylorr.com>
---
pack-bitmap-write.c | 23 +++++++++++++++--------
1 file changed, 15 insertions(+), 8 deletions(-)
diff --git a/pack-bitmap-write.c b/pack-bitmap-write.c
index 1c8070f99c0..2d5ff8fd406 100644
--- a/pack-bitmap-write.c
+++ b/pack-bitmap-write.c
@@ -456,10 +456,10 @@ static void bitmap_builder_clear(struct bitmap_builder *bb)
static int fill_bitmap_tree(struct bitmap_writer *writer,
struct bitmap *bitmap,
- struct tree *tree)
+ struct tree *tree,
+ uint32_t pos)
{
int found;
- uint32_t pos;
struct tree_desc desc;
struct name_entry entry;
@@ -467,9 +467,6 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
* If our bit is already set, then there is nothing to do. Both this
* tree and all of its children will be set.
*/
- pos = find_object_pos(writer, &tree->object.oid, &found);
- if (!found)
- return -1;
if (bitmap_get(bitmap, pos))
return 0;
bitmap_set(bitmap, pos);
@@ -482,8 +479,12 @@ static int fill_bitmap_tree(struct bitmap_writer *writer,
while (tree_entry(&desc, &entry)) {
switch (object_type(entry.mode)) {
case OBJ_TREE:
+ pos = find_object_pos(writer, &entry.oid, &found);
+ if (!found)
+ return -1;
if (fill_bitmap_tree(writer, bitmap,
- lookup_tree(writer->repo, &entry.oid)) < 0)
+ lookup_tree(writer->repo,
+ &entry.oid), pos) < 0)
return -1;
break;
case OBJ_BLOB:
@@ -575,8 +576,14 @@ static int fill_bitmap_commit(struct bitmap_writer *writer,
}
while (tree_queue->nr) {
- if (fill_bitmap_tree(writer, ent->bitmap,
- prio_queue_get(tree_queue)) < 0)
+ struct tree *t = prio_queue_get(tree_queue);
+ int found;
+
+ pos = find_object_pos(writer, &t->object.oid, &found);
+ if (!found)
+ return -1;
+
+ if (fill_bitmap_tree(writer, ent->bitmap, t, pos) < 0)
return -1;
}
return 0;
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply related
* [PATCH v2 0/8] pack-bitmap-write: speed up bitmap generation
From: Taylor Blau @ 2026-05-27 19:55 UTC (permalink / raw)
To: git; +Cc: Junio C Hamano, Jeff King, Elijah Newren, Derrick Stolee
In-Reply-To: <cover.1779207127.git.me@ttaylorr.com>
Here is a reroll of my series to improve the performance of reachability
bitmap generation, focusing on very large repositories and the penalty
to generate pseudo-merge reachability bitmaps.
The series is largely unchanged since last time. Notable changes in this
round include:
- minor refactoring in the pair of patches which consolidate the
`find_object_pos()` success path and introduce the object position
cache during bitmap fills, and
- dropping a stale paragraph from the final patch's message, which
described follow-up commits that are no longer part of this series.
As usual, a range-diff against v1 is included below for convenience.
Thanks in advance for your review!
Taylor Blau (8):
pack-bitmap: pass object position to `fill_bitmap_tree()`
pack-bitmap: check subtree bits before recursing
pack-bitmap: reuse stored selected bitmaps
pack-bitmap: consolidate `find_object_pos()` success path
pack-bitmap: cache object positions during fill
pack-bitmap: sort bitmaps before XORing
pack-bitmap: remember pseudo-merge parents
pack-bitmap: build pseudo-merge bitmaps after regular bitmaps
pack-bitmap-write.c | 431 +++++++++++++++++++++++++++++++++++++-------
pack-bitmap.h | 7 +
2 files changed, 377 insertions(+), 61 deletions(-)
Range-diff against v1:
1: 13191c19b91 = 1: ad025810ab3 pack-bitmap: pass object position to `fill_bitmap_tree()`
2: 7d6d1cec0dd = 2: 59da63d0330 pack-bitmap: check subtree bits before recursing
3: 6e1f6bef5f6 = 3: f13d65c0ad9 pack-bitmap: reuse stored selected bitmaps
4: c9a56066094 ! 4: 856aa3a6ab7 pack-bitmap: consolidate `find_object_pos()` success path
@@ Commit message
Signed-off-by: Taylor Blau <me@ttaylorr.com>
## pack-bitmap-write.c ##
+@@ pack-bitmap-write.c: static uint32_t find_object_pos(struct bitmap_writer *writer,
+ const struct object_id *oid, int *found)
+ {
+ struct object_entry *entry;
++ uint32_t pos;
+
+ entry = packlist_find(writer->to_pack, oid);
+ if (entry) {
@@ pack-bitmap-write.c: static uint32_t find_object_pos(struct bitmap_writer *writer,
if (writer->midx)
base_objects = writer->midx->num_objects +
5: e43ef6a42d1 ! 5: 70dfa80d543 pack-bitmap: cache object positions during fill
@@ pack-bitmap-write.c: void bitmap_writer_push_commit(struct bitmap_writer *writer
const struct object_id *oid, int *found)
{
struct object_entry *entry;
-+ uint32_t pos;
-+
+ uint32_t pos;
+
+ bitmap_writer_init_pos_cache(writer);
+
+ if (find_cached_object_pos(writer, oid, &pos)) {
@@ pack-bitmap-write.c: void bitmap_writer_push_commit(struct bitmap_writer *writer
+ *found = 1;
+ return pos;
+ }
-
++
entry = packlist_find(writer->to_pack, oid);
if (entry) {
uint32_t base_objects = 0;
6: b0a4f31353a = 6: b1184792d23 pack-bitmap: sort bitmaps before XORing
7: 0bd88e6a096 = 7: 673b6262911 pack-bitmap: remember pseudo-merge parents
8: 30ce254312c ! 8: 8722242f1bb pack-bitmap: build pseudo-merge bitmaps after regular bitmaps
@@ Commit message
portion of history reachable by one or more pseudo-merge(s), but not by
any non-pseudo-merge commit selected for bitmapping.
- Now that we have decoupled how we generate pseudo-merges from their
- representation, the following commits will improve the API around
- specifying pseudo-merge groupings during bitmap generation.
-
Signed-off-by: Taylor Blau <me@ttaylorr.com>
## pack-bitmap-write.c ##
base-commit: c3d7ca7d982efc3a848fd85f34e867cfc0a99479
--
2.54.0.rc1.84.g1cf18622df7
^ permalink raw reply
* Re: [PATCH 8/8] pack-bitmap: build pseudo-merge bitmaps after regular bitmaps
From: Taylor Blau @ 2026-05-27 19:24 UTC (permalink / raw)
To: Jeff King; +Cc: git, Junio C Hamano, Elijah Newren, Derrick Stolee
In-Reply-To: <20260527102534.GH981444@coredump.intra.peff.net>
On Wed, May 27, 2026 at 06:25:34AM -0400, Jeff King wrote:
> > It struggles, however, to efficiently generate pseudo-merge bitmaps.
> > Unlike ordinary commits for which the above algorithm is designed,
> > pseudo-merges don't represent any "real" commit in history, just a
> > grouping of non-bitmapped reference tips. In that sense, their first
> > parent is just a part of a larger set, and treating them like ordinary
> > selected commits imposes a significant slow-down when generating bitmaps
> > with pseudo-merges enabled.
>
> This is a great explanation of the problem, and especially this:
>
> > In other words, we pay a nearly ~5 minute penalty to generate
> > pseudo-merge bitmaps, but only save ~50 seconds during traversal.
>
> makes it clear that we're doing something sub-optimal. And it points us
> in the right direction, since that traversal should be able to generate
> the pseudo-merge bitmap we need in the first place! So that should be
> our goal to work towards.
>
> > Instead, build the regular selected commit bitmaps first, considering
> > only non-pseudo-merge commits in `bitmap_builder_init()`. Once those
> > bitmaps have been stored, build each pseudo-merge bitmap separately and
> > attach its parent and object bitmaps to the corresponding pseudo-merge
> > entry before writing the extension.
>
> And then this solution follows naturally from the earlier explanations.
> Good.
Thanks. For as clear as this sounds now, finding this approach took me
longer than I'd like to admit. I'm satisfied, however, with the result.
> In some ways this goes back to the pre-v2.31 way of generating bitmaps,
> which is to just traverse for each bitmap independently. But as you
> note, the whole idea of pseudo-merge bitmaps is that they aren't
> overlapping in any meaningful way. So doing one fill-in traversal per
> pseudo-merge makes sense, and hopefully we hit enough real bitmaps that
> it's not too costly.
Exactly!
> > As a result, the overhead cost for generating pseudo-merges in the above
> > configuration is much smaller:
> >
> > +------------------+-----------------+---------------+-------------------+
> > | | no pseudo-merge | pseudo-merges | Delta |
> > | | | (HEAD) | |
> > +------------------+-----------------+---------------+-------------------+
> > | elapsed | 294.1 s | 328.4 s | +34.3 s (+11.7%) |
> > | cycles | 1,365.5 B | 1,529.3 B | +163.7 B (+12.0%) |
> > | instructions | 1,389.8 B | 1,552.8 B | +163.0 B (+11.7%) |
> > | CPI | 0.983 | 0.985 | +0.002 (+0.2%) |
> > +------------------+-----------------+---------------+-------------------+
>
> Nice. The time savings are going to depend on how many pseudo-merges we
> generate, I think. And I'd guess that the numbers above come from making
> one big pseudo-merge bitmap, per the config you showed earlier. But you
> probably only want a handful of them in any repo, so hopefully it
> doesn't scale _too_ badly.
That's right, though see below for more thoughts on scaling...
> > Recall that at the start of this series, generating reachability bitmaps
> > took 612.5 seconds *without* pseudo-merges. With this commit, it is
> > still ~46.38% *faster* to generate reachability bitmaps *with*
> > pseudo-merges than it was to generate bitmaps wihtout them at the
> > beginning of this series.
>
> Sure, though 612.5 seconds is all in the distant past. We only care
> about 294.1 seconds now. ;)
Heh ;-). Naturally, I agree here, but wanted to include it for context.
I wanted to point out that the accumulated changes in this series make
it cheaper to generate bitmaps with pseudo-merges now than it was to
generate bitmaps without them before.
> More seriously, I do think the interesting question here is how the time
> scales for various pseudo-merge configurations. I don't know if we have
> any real operational experience with them yet. The original idea is that
> you might slice up the ref space into a few chunks. I'd guess that the
> old code performed badly-ish overall, but the time did not grow all that
> much as you increased the number of chunks. But with the new code, I
> suspect that the cost grows more linearly with number of chunks. That's
> just a guess, though.
I'm not aware of any large-scale deployments of pseudo-merge bitmaps.
This series is written (in part) of the hopes of making one ;-). I think
your intuition on the old code matches my own.
Below are some numbers that give you a sense of how the runtime scales
with the number of pseudo-merges. I'm relying exclusively on "stable"
pseudo-merges here since they have more predictable bucketing behavior,
though note that there isn't an exact way to dial in the number of these
so-called "stable" pseudo-merge groups. We can only control their *size*
(in terms of number of parents), so I ran the harness which produced the
above code with powers of 10 between [10^3, 10^6].
Results are as follows:
+------------+-------+----------+
| stableSize | count | time (s) |
+------------+-------+----------+
| 1000000 | 1 | 34.963 |
| 100000 | 3 | 36.954 |
| 10000 | 26 | 221.963 |
| 1000 | 252 | 2779.373 |
+------------+-------+----------+
Which scales roughly like O(x^1.165) (the best fit function I could find
was t(n) = 25.18 + 4.386 * n^1.165, where 'n' is the number of
pseudo-merges, and t(n) is the time it took to generate them).
So it does grow faster than linearly, but it's not too bad. The jump
from 26 to 252 pseudo-merges is pretty significant, though, but having
that many pseudo-merges is probably not something that we would want to
do in practice.
> The other thing we hope for with pseudo-merges is that the chunks are
> selected such that most of the chunks don't change (because they are
> composed of old, stable refs). So in subsequent bitmap generations, we
> can either reuse them either verbatim or as a starting point (if there
> were only additions). But all of that is going to be heuristic and
> depend on your config, the changes the repo sees over time, and so on.
>
> So I don't know if we'd really have good numbers on that.
We don't, and it is somewhat of a pain to simulate. I think the proof
will be in the pudding, so to speak.
> > Now that we have decoupled how we generate pseudo-merges from their
> > representation, the following commits will improve the API around
> > specifying pseudo-merge groupings during bitmap generation.
>
> I think we're at patch 8/8 here. I guess you have more to come
> eventually, but for now this part is just misleading. ;)
Yeah, I cleaved this off of a larger series to make the pseudo-merge API
a little easier to reason about and less clunky to use. But I ended up
hoarding some of those patches, and apparently forgot to adjust the
message here. Thanks for spotting.
Thanks,
Taylor
^ permalink raw reply
* [PATCH v2 3/3] daemon: guard NULL REMOTE_PORT in execute() logging
From: Sebastien Tardif via GitGitGadget @ 2026-05-27 18:18 UTC (permalink / raw)
To: git; +Cc: Patrick Steinhardt, Sebastien Tardif, Sebastien Tardif
In-Reply-To: <pull.2300.v2.git.git.1779905911.gitgitgadget@gmail.com>
From: Sebastien Tardif <sebtardif@ncf.ca>
REMOTE_ADDR and REMOTE_PORT are both set by the same code path in
handle(), so neither should be NULL independently. However, the
existing code checks REMOTE_ADDR before the loginfo() call but not
REMOTE_PORT. If REMOTE_PORT were unset, NULL would be passed to
printf's %s, which is undefined behavior.
Add a fallback string for the NULL case, matching the existing
REMOTE_ADDR guard for consistency.
Signed-off-by: Sebastien Tardif <sebtardif@ncf.ca>
---
daemon.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/daemon.c b/daemon.c
index 103c08d868..78cca8673f 100644
--- a/daemon.c
+++ b/daemon.c
@@ -753,7 +753,7 @@ static int execute(void)
struct strvec env = STRVEC_INIT;
if (addr)
- loginfo("Connection from %s:%s", addr, port);
+ loginfo("Connection from %s:%s", addr, port ? port : "?");
set_keep_alive(0);
alarm(init_timeout ? init_timeout : timeout);
--
gitgitgadget
^ permalink raw reply related
* [PATCH v2 2/3] daemon: fix IPv6 address truncation in ip2str()
From: Sebastien Tardif via GitGitGadget @ 2026-05-27 18:18 UTC (permalink / raw)
To: git; +Cc: Patrick Steinhardt, Sebastien Tardif, Sebastien Tardif
In-Reply-To: <pull.2300.v2.git.git.1779905911.gitgitgadget@gmail.com>
From: Sebastien Tardif <sebtardif@ncf.ca>
The sockaddr struct size (ai_addrlen) is passed as the output buffer
size to inet_ntop(). For IPv6, sizeof(sockaddr_in6) is 28 bytes but
INET6_ADDRSTRLEN is 46, so long IPv6 addresses are silently truncated.
Fix this by passing sizeof(ip) instead, which is the actual size of
the destination buffer. Drop the now-unused len parameter from
ip2str() and update all callers.
Signed-off-by: Sebastien Tardif <sebtardif@ncf.ca>
---
daemon.c | 14 +++++++-------
1 file changed, 7 insertions(+), 7 deletions(-)
diff --git a/daemon.c b/daemon.c
index 80fa0226d8..103c08d868 100644
--- a/daemon.c
+++ b/daemon.c
@@ -947,7 +947,7 @@ struct socketlist {
size_t alloc;
};
-static const char *ip2str(int family, struct sockaddr *sin, socklen_t len)
+static const char *ip2str(int family, struct sockaddr *sin)
{
#ifdef NO_IPV6
static char ip[INET_ADDRSTRLEN];
@@ -958,11 +958,11 @@ static const char *ip2str(int family, struct sockaddr *sin, socklen_t len)
switch (family) {
#ifndef NO_IPV6
case AF_INET6:
- inet_ntop(family, &((struct sockaddr_in6*)sin)->sin6_addr, ip, len);
+ inet_ntop(family, &((struct sockaddr_in6*)sin)->sin6_addr, ip, sizeof(ip));
break;
#endif
case AF_INET:
- inet_ntop(family, &((struct sockaddr_in*)sin)->sin_addr, ip, len);
+ inet_ntop(family, &((struct sockaddr_in*)sin)->sin_addr, ip, sizeof(ip));
break;
default:
xsnprintf(ip, sizeof(ip), "<unknown>");
@@ -1019,14 +1019,14 @@ static int setup_named_sock(char *listen_addr, int listen_port, struct socketlis
if (bind(sockfd, ai->ai_addr, ai->ai_addrlen) < 0) {
logerror("Could not bind to %s: %s",
- ip2str(ai->ai_family, ai->ai_addr, ai->ai_addrlen),
+ ip2str(ai->ai_family, ai->ai_addr),
strerror(errno));
close(sockfd);
continue; /* not fatal */
}
if (listen(sockfd, 5) < 0) {
logerror("Could not listen to %s: %s",
- ip2str(ai->ai_family, ai->ai_addr, ai->ai_addrlen),
+ ip2str(ai->ai_family, ai->ai_addr),
strerror(errno));
close(sockfd);
continue; /* not fatal */
@@ -1080,7 +1080,7 @@ static int setup_named_sock(char *listen_addr, int listen_port, struct socketlis
if ( bind(sockfd, (struct sockaddr *)&sin, sizeof sin) < 0 ) {
logerror("Could not bind to %s: %s",
- ip2str(AF_INET, (struct sockaddr *)&sin, sizeof(sin)),
+ ip2str(AF_INET, (struct sockaddr *)&sin),
strerror(errno));
close(sockfd);
return 0;
@@ -1088,7 +1088,7 @@ static int setup_named_sock(char *listen_addr, int listen_port, struct socketlis
if (listen(sockfd, 5) < 0) {
logerror("Could not listen to %s: %s",
- ip2str(AF_INET, (struct sockaddr *)&sin, sizeof(sin)),
+ ip2str(AF_INET, (struct sockaddr *)&sin),
strerror(errno));
close(sockfd);
return 0;
--
gitgitgadget
^ permalink raw reply related
* [PATCH v2 1/3] daemon: fix IPv6 address corruption in lookup_hostname()
From: Sebastien Tardif via GitGitGadget @ 2026-05-27 18:18 UTC (permalink / raw)
To: git; +Cc: Patrick Steinhardt, Sebastien Tardif, Sebastien Tardif
In-Reply-To: <pull.2300.v2.git.git.1779905911.gitgitgadget@gmail.com>
From: Sebastien Tardif <sebtardif@ncf.ca>
getaddrinfo() is called with AF_UNSPEC hints, so it may return IPv6
results. However, the code unconditionally casts ai_addr to
sockaddr_in and passes AF_INET to inet_ntop(). On IPv6-only hosts,
this reads from the wrong struct offset, producing garbage IP
addresses.
Fix this by checking ai_family and extracting the address pointer
into a local variable before calling inet_ntop() once with the
correct family. Die on unexpected address families.
Signed-off-by: Sebastien Tardif <sebtardif@ncf.ca>
---
daemon.c | 15 +++++++++++++--
1 file changed, 13 insertions(+), 2 deletions(-)
diff --git a/daemon.c b/daemon.c
index 0a7b1aae44..80fa0226d8 100644
--- a/daemon.c
+++ b/daemon.c
@@ -674,9 +674,20 @@ static void lookup_hostname(struct hostinfo *hi)
gai = getaddrinfo(hi->hostname.buf, NULL, &hints, &ai);
if (!gai) {
- struct sockaddr_in *sin_addr = (void *)ai->ai_addr;
+ void *addr;
+
+ if (ai->ai_family == AF_INET) {
+ struct sockaddr_in *sa = (void *)ai->ai_addr;
+ addr = &sa->sin_addr;
+ } else if (ai->ai_family == AF_INET6) {
+ struct sockaddr_in6 *sa6 = (void *)ai->ai_addr;
+ addr = &sa6->sin6_addr;
+ } else {
+ die("unexpected address family: %d",
+ ai->ai_family);
+ }
- inet_ntop(AF_INET, &sin_addr->sin_addr,
+ inet_ntop(ai->ai_family, addr,
addrbuf, sizeof(addrbuf));
strbuf_addstr(&hi->ip_address, addrbuf);
--
gitgitgadget
^ permalink raw reply related
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox