JGit UploadPack can spend quadratic CPU and memory peeling shared loose tag chains

[N0zoM1z0]

Version

v7.8.0.202609011348-r-10-g87ec21000

Operating System

Linux/Unix

Bug description

JGit's UploadPack advertisement path can perform the same deep annotated-tag
peel once for every loose ref that points to the chain. A repository with D
nested annotated tags and R loose tag refs sharing the top tag therefore
causes O(D * R) tag traversals during a single advertisement, while the
repository stores only O(D + R) tag and ref records.

The request reaches this work before the client supplies any wants. In a
service that accepts repository content and serves it through JGit's
UploadPack API, a user can create this repository shape and cause each fetch
connection to pay the repeated peeling cost.

The v0/v1 path enters the relevant code through
UploadPack.sendAdvertisedRefs(),
which enables tag dereferencing and passes the advertised refs to
RefAdvertiser.send().
RefAdvertiser.send() emits the original row and, for an unpeeled ref, calls
repository.getRefDatabase().peel(ref) before emitting the peeled row. The
same advertiser is used by protocol v2 when ls-refs includes peel, through
UploadPack.lsRefsV2().

For a loose ref,
RefDirectory.peel() and doPeel()
create a RevWalk, parse the ref's object, and call
RevWalk.peel().
RevWalk.peel() follows each annotated-tag header until it reaches the first
non-tag object. A ref at the top of a chain of depth D consequently causes
D tag transitions and object-header parses.

RefDirectory.peel() updates the loose-ref cache after peeling, using the
cache replacement path
and LooseUnpeeled.peel().
The collection passed to the current RefAdvertiser.send() invocation already
contains the original unpeeled Ref instances. Replacing entries in the ref
database does not replace those objects in the active collection, so the next
shared ref starts another fresh RevWalk over the same tag chain.

The reproducing graph is:

one commit <- D nested annotated tags <- R loose refs
    -> UploadPack.sendAdvertisedRefs()
    -> RefAdvertiser.send()
    -> R calls to RefDirectory.peel()
    -> R fresh RevWalk.peel() traversals of D tags
    -> D * R tag transitions

The generated N=2,048 repository contains 2,048 nested tag objects and 2,048
loose tag refs, occupies 343,360 apparent bytes across 4,102 files, and uses
17,944,576 bytes of measured filesystem allocation in the loose workspace.
The first JGit advertisement returns the complete expected output while using
141.624 CPU seconds and reaching 736,063,488 bytes of container memory.

Actual behavior

The target accepts the advertisement-only exchange, returns all expected
original and peeled tag rows, and pays the repeated traversal cost. The
high-scale result is:

OBSERVED target=jgit storage=loose depth=2048 refs=2048 status=accepted returncode=0 rows=4096 expected_rows=4096 object_graph_validation=passed cpu_seconds=141.624499 wall_seconds=141.337551 peak_memory_bytes=736063488

The same valid repository and the same independent advertisement oracle give
the following controls:

Target	Storage	D	R	Apparent bytes	CPU seconds	Wall seconds	Peak memory bytes
JGit 7.8.0.202609011348-r	loose	2,048	2,048	343,360	141.624499	141.337551	736,063,488
JGit 7.8.0.202609011348-r	packed, fully peeled	2,048	2,048	476,541	1.235104	0.935447	61,812,736
Git 2.55.0	loose	2,048	2,048	343,360	0.152700	0.794308	7,200,768

At N=2,048, the JGit loose-ref case uses approximately 927 times the
container CPU, 178 times the wall time, and 102 times the peak memory of the
Git 2.55.0 control. The packed-ref control retains the same 4,096 advertised
tag rows and the same object graph without the repeated loose-ref traversal.

The fixed-axis runs isolate the two dimensions of the behavior:

Case	Target	D	R	CPU seconds	Wall seconds	Peak memory bytes
depth-only	JGit	1,024	1	2.562622	4.001704	79,446,016
ref-fanout-only	JGit	1	1,024	2.783062	4.131080	114,102,272
depth-only	Git 2.55.0	1,024	1	0.041486	0.444677	5,087,232
ref-fanout-only	Git 2.55.0	1	1,024	0.044596	0.415964	6,852,608

All rows above were accepted with the expected 2R tag advertisement rows.

Expected behavior

The advertisement path should peel each distinct tag object at most once per
advertisement and reuse the result for every ref that reaches that object. The
protocol output should still contain the original and peeled row for each ref.

The work for a shared chain should therefore be bounded by the number of
distinct tag objects plus the number of advertised refs, rather than by their
product. A per-advertisement object-ID peel cache, a shared reader and peel
cache, or materializing peeled values before entering RefAdvertiser.send()
would preserve the output while removing the repeated traversal. A bounded
peel budget with a request-level error is another way to keep a malformed or
pathological repository from consuming an unbounded worker budget.

Relevant log output

target=jgit version=7.8.0.202609011348-r source_commit=87ec2100083ffc894bedd1e3f0d76b7f10e45ed6
fixture=loose depth=2048 refs=2048 status=accepted returncode=0 expected_rows=4096 observed_rows=4096
container_cpu_seconds=141.624499 wall_seconds=141.337551 container_memory_peak_bytes=736063488
object_graph_validation=passed

target=git-core version=2.55.0 source_commit=e9019fcafe0040228b8631c30f97ae1adb61bcdc
fixture=loose depth=2048 refs=2048 status=accepted returncode=0 expected_rows=4096 observed_rows=4096
container_cpu_seconds=0.152700 wall_seconds=0.794308 container_memory_peak_bytes=7200768
object_graph_validation=passed

target=jgit version=7.8.0.202609011348-r source_commit=87ec2100083ffc894bedd1e3f0d76b7f10e45ed6
fixture=packed depth=2048 refs=2048 status=accepted returncode=0 expected_rows=4096 observed_rows=4096
container_cpu_seconds=1.235104 wall_seconds=0.935447 container_memory_peak_bytes=61812736
object_graph_validation=passed


The complete recorded summary is [`attachments/run.log`](attachments/run.log).

Other information

The attached reproducer is standalone. From the directory containing the
attachments/ directory, run:

sh attachments/reproduce.sh

The prerequisites are Docker, Python 3.10 or newer, and network access for
the initial image builds. The package is self-contained: it builds the JGit
probe from the pinned Maven dependency and builds Git 2.55.0 from the pinned
upstream source tarball, whose SHA-256 is verified by Dockerfile.git-core.
The execution uses only the files in attachments/ and the listed
prerequisites.

An individual high-scale case can be run after the two images have been built:

python3 attachments/jgit_upload_pack_peel_reproduce.py \
  --target jgit --image gitbombs-upload-pack-peel:jgit-7.8.0 \
  --depth 2048 --refs 2048 --storage loose \
  --output attachments/results/jgit-loose-n02048.json

The runner creates the repository with the Python standard library, validates
every object checksum and header, verifies tag declarations and chain
termination, verifies that all refs share the expected top tag, and checks the
exact advertisement row count after the target operation. JGit receives EOF
after the initial advertisement. Git-core receives a valid 0000 flush packet
so that the advertisement-only exchange terminates through the protocol. Both
probes enter the advertisement path before any wants are supplied.

The complete diagonal and control matrix is included in
attachments/results/. The Git-core control is built from the pinned
e9019fcafe0040228b8631c30f97ae1adb61bcdc
source revision. The official Git source installation page
provides the corresponding 2.55.0 release source.

The observed loose diagonal scales as expected for a product of the two input
dimensions: JGit uses 9.830496 CPU seconds at D=R=512, 37.686551 seconds at
D=R=1,024, and 141.624499 seconds at D=R=2,048. The three points produce an
observed exponent of approximately 1.93 with N, consistent with one deep peel
per shared ref. The repository representation remains linear in the number of
tag objects and refs.

The full evidence set is included in the accompanying archive. The principal
files are:

• reproduce.sh, the complete replay entrypoint;
• README.md, the standalone execution notes;
• jgit_upload_pack_peel_reproduce.py, the fixture builder, validator, and runner;
• Dockerfile.jgit, pom.xml, and UploadPackProbe.java, the pinned JGit target;
• Dockerfile.git-core and git-core-upload-pack-entrypoint.sh, the Git control target;
• measure.sh, the in-container process measurement wrapper;
• loose-n02048.json, packed-n02048.json, and git-core-loose-n02048.json, the high-scale measurements;
• run.log, the compact log corresponding to the measurements quoted above.

Attachments

attachments.zip contains the complete attachments/
directory, including the standalone reproducer, pinned target build files,
validation code, logs, and JSON measurements.