Re: [PATCH v3] promisor-remote: prevent lazy-fetch recursion in child fetch

[Paul Tarjan <paul@paultarjan.com>]

Jeff King <peff@peff.net> writes:

> It would be nice to confirm that's what's going on, though (and it isn't
> really a thin pack). If the problem can be reproduced, I don't suppose
> we have a GIT_TRACE_PACKET output from a failing instance? That would
> confirm that we're correctly using the noop negotiation.

Yeah. I couldn't capture one live during the incident, but I did a
clean-room reproduction afterward: empty bare repo, git remote add
origin pointing at the same GitHub monorepo, then the exact argv
from fetch_objects() with a tree SHA pulled from one of the
.promisor sidecars written during the incident:

  $ git -c fetch.negotiationAlgorithm=noop fetch origin \
        --no-tags --no-write-fetch-head --recurse-submodules=no \
        --filter=blob:none --stdin <<< "$TREE_OID"

  packet:        fetch< version 2
  packet:        fetch< agent=git/github-94ec3a8682aa-Linux
  packet:        fetch< ls-refs=unborn
  packet:        fetch< fetch=shallow wait-for-done filter
  packet:        fetch< server-option
  packet:        fetch< object-format=sha1
  packet:        fetch< 0000
  packet:        fetch> command=fetch
  packet:        fetch> agent=git/2.51.2-Linux
  packet:        fetch> object-format=sha1
  packet:        fetch> 0001
  packet:        fetch> thin-pack
  packet:        fetch> no-progress
  packet:        fetch> ofs-delta
  packet:        fetch> filter blob:none
  packet:        fetch> want 086faa42a038f2e4a1b5e395cde544f8f3c6a9a5
  packet:        fetch> done
  packet:        fetch> 0000
  packet:        fetch< packfile
  packet:     sideband< PACK ...
  packet:     sideband< 0000

Zero have lines, noop negotiation doing its thing.

Two interesting bits:

1. The client sends thin-pack unconditionally (fetch-pack.c doesn't
   check what negotiation algorithm is in use). So the server is
   allowed to send a thin pack. With zero haves it has nothing to
   thin against, but nothing on the wire actually forbids it.

2. filter blob:none is on the wire -- hardcoded by fetch_objects().
   Combined with thin-pack, this gives the server a way to end up
   omitting an object that happens to be a delta base.

For this particular tree GitHub responded cleanly (5 trees, no
deltas, 2701 bytes), so whatever triggers the REF_DELTA depends on
the specific objects being fetched and how they're stored
server-side.

> But it _can_ send deltas against objects which are part of the backfill
> itself. Normally we'd send those as OFS_DELTA, because they're both in
> the same output pack. But there are cases where we might not:
>
>   - the verbatim pack-reuse code will sometimes rewrite ofs-delta into
>     ref-delta. I don't remember all of the cases where this might
>     happen. Certainly if the client hasn't claimed to support
>     ofs-deltas, but I think maybe some other cases? I'd have to dig into
>     it.

I think it's (b). What's interesting is that Jonathan Tan flagged
exactly this risk when he introduced the prefetch call.
8a30a1efd1 ("index-pack: prefetch missing REF_DELTA bases",
2019-05-14):

    Support for lazy fetching should still generally be turned off
    in index-pack because it is used as part of the lazy fetching
    process itself (if not, infinite loops may occur), but we do
    need to fetch the REF_DELTA bases. (When fetching REF_DELTA
    bases, it is unlikely that those are REF_DELTA themselves,
    because we do not send "have" when making such fetches.)

So the "infinite loops may occur" door was left open deliberately,
on the argument that it's unlikely. My patch just closes it.

Here's what I think went wrong in practice: fetch_objects()
hardcodes --filter=blob:none. When the want is a tree, the server
walks tree reachability and assembles potentially millions of tree
objects with no blobs. If pack-reuse passes through an object
stored server-side as OFS_DELTA against a blob, it comes out as
REF_DELTA and the blob base gets filtered out by blob:none.

I have a live ps snapshot from the incident showing the chain:

  3719679  git -c fetch.negotiationAlgorithm=noop fetch origin \
               --no-tags --no-write-fetch-head \
               --recurse-submodules=no --filter=blob:none --stdin
  3725911  git index-pack --stdin --fix-thin --keep=fetch-pack \
               3719679 on <host> --promisor --pack_header=2,7535361
  3726936  git -c fetch.negotiationAlgorithm=noop fetch origin \
               --no-tags --no-write-fetch-head \
               --recurse-submodules=no --filter=blob:none --stdin

--keep embeds the parent PID, so the chain is clear: lazy-fetch
(3719679) -> index-pack (3725911, 7,535,361 objects) -> depth-2
lazy-fetch (3726936). 7.5M objects is about right for wanting a
single tree with no haves and filter=blob:none -- you get the
entire commit+tree closure minus blobs. One REF_DELTA against a
filtered blob in 7.5M objects and you're recursing.

> Now there's a catch: the pack is not really thin, and so index-pack
> should not need to do an extra backfill request in order to get the base
> object.

Actually, the pack IS thin in this case -- the REF_DELTA's base is
a blob that the server filtered out because of blob:none. The base
isn't in the pack at all. fix_unresolved_deltas() correctly sees it
as unresolved and calls promisor_remote_get_direct().

> If that's what is happening, then I _think_ Paul's patch will do the
> right thing. We'd say "no, we don't have that object" without doing the
> backfill, and then eventually find it as part of the final resolution.

Right, that's what happens. The child hits the guard at the top of
fetch_objects() and bails with "lazy fetching disabled". The
depth-1 index-pack can't resolve the delta, which is the correct
outcome -- retrying the same noop fetch would just get the same
response.

I also wrote a deterministic local reproducer (no network needed)
that shows the recursion directly. Two scripts, needs python3 + git,
works on Linux and macOS. Ran it just now:

repro-depth1.sh sets up a local bare server with two similar blobs,
a blob:none partial-clone client, and a hand-crafted 68-byte thin
pack with one REF_DELTA against a promised-but-absent blob:

  === without GIT_NO_LAZY_FETCH (current git) ===
  index-pack invocations: 2
  lazy-fetch spawns:      1

  === with GIT_NO_LAZY_FETCH=1 (what the patch sets) ===
  index-pack invocations: 1
  lazy-fetch spawns:      0

repro-unbounded.sh goes further: uploadpack.packObjectsHook always
returns the same thin pack, so every lazy-fetch spawns another.
Watchdog kills it at depth 50:

  === without patch ===
  recursion depth reached: 55
  index-pack invocations:  55
  tmp_pack_* on disk:      55

  === with GIT_NO_LAZY_FETCH=1 (the patch) ===
  recursion depth:         0
  index-pack invocations:  1
  tmp_pack_* on disk:      0

Those tmp_pack_* files are the disk growth -- each index-pack
streams to a tmpfile, blocks in fix_unresolved_deltas() to
lazy-fetch the base, and never gets to rename it. In the real
incident each was ~1.4 GB.

Scripts below.

--- >8 --- repro-depth1.sh --- >8 ---

#!/bin/bash
# Deterministic depth-1 recursion proof for promisor-remote lazy-fetch bug.
# No network. Runs in ~1 second.
#
# Mechanism:
#   - Local bare server with two similar blobs; client is a blob:none
#     partial clone (both blobs promised, neither local).
#   - Craft a 68-byte thin pack by hand: one REF_DELTA object whose base
#     SHA is one of the promised-but-absent blobs.
#   - Feed to `git -C client index-pack --stdin --fix-thin`.
#   - fix_unresolved_deltas() sees the unresolved REF_DELTA, calls
#     promisor_remote_get_direct() for the base, which spawns
#     `git -c fetch.negotiationAlgorithm=noop fetch ... --stdin`.
#   - That child fetch spawns its own index-pack --fix-thin.
#   - GIT_TRACE shows the nested spawn.

set -euo pipefail

W="${TMPDIR:-/tmp}/promisor-recursion-demo"
rm -rf "$W"; mkdir -p "$W"; cd "$W"

git -c init.defaultBranch=main init -q --bare server.git
git -C server.git config uploadpack.allowFilter true
git -C server.git config uploadpack.allowAnySHA1InWant true
git -c init.defaultBranch=main init -q work
(
    cd work
    python3 -c "print('\n'.join('shared line %d ' * 4 % (i,i,i,i) for i in range(200)))" > f
    git add f; git commit -qm base
    python3 -c "print('\n'.join('shared line %d ' * 4 % (i,i,i,i) for i in range(200))); print('extra')" > f
    git add f; git commit -qm delta
    git push -q ../server.git main
)

printf '%s\n%s\n' "$(git -C work rev-parse HEAD~1:f)" "$(git -C work rev-parse HEAD:f)" | \
    git -C server.git pack-objects --stdout --delta-base-offset > both.pack

python3 << 'PYEOF'
import struct, zlib, hashlib

with open('both.pack', 'rb') as f:
    data = f.read()
assert data[:4] == b'PACK' and struct.unpack('>I', data[8:12])[0] == 2

def parse_hdr(data, pos):
    b = data[pos]; otype = (b >> 4) & 7; sz = b & 0xf; sh = 4; p = pos
    while b & 0x80:
        p += 1; b = data[p]; sz |= (b & 0x7f) << sh; sh += 7
    return otype, sz, p + 1

def zlib_end(data, pos):
    d = zlib.decompressobj(); p = pos
    while p < len(data):
        chunk = data[p:p+512]; d.decompress(chunk)
        if d.unused_data: return p + len(chunk) - len(d.unused_data)
        if d.eof: return p + len(chunk)
        p += len(chunk)
    return p

t1, s1, d1 = parse_hdr(data, 12)
if t1 == 6:
    p = d1; b = data[p]; p += 1
    while b & 0x80: b = data[p]; p += 1
    e1 = zlib_end(data, p)
else:
    e1 = zlib_end(data, d1)
t2, s2, d2 = parse_hdr(data, e1)

if t1 == 3 and t2 == 6:
    base_raw = zlib.decompress(data[d1:e1])
    delta_sz, delta_hdr_end = s2, d2
elif t1 == 6 and t2 == 3:
    base_raw = zlib.decompress(data[d2:zlib_end(data, d2)])
    delta_sz, delta_hdr_end = s1, d1
else:
    raise SystemExit(f"expected one blob + one OFS_DELTA, got types {t1},{t2}")

base_sha = hashlib.sha1(f"blob {len(base_raw)}\0".encode() + base_raw).digest()

p = delta_hdr_end; b = data[p]; p += 1
while b & 0x80: b = data[p]; p += 1
delta_zlib = data[p:zlib_end(data, p)]

sz = delta_sz
hb = [(7 << 4) | (sz & 0xf)]; sz >>= 4
while sz: hb[-1] |= 0x80; hb.append(sz & 0x7f); sz >>= 7
thin = b'PACK' + struct.pack('>II', 2, 1) + bytes(hb) + base_sha + delta_zlib
thin += hashlib.sha1(thin).digest()
with open('thin.pack', 'wb') as f: f.write(thin)
print(f"thin.pack: {len(thin)} bytes, REF_DELTA base={base_sha.hex()}")
PYEOF

git clone -q --no-local --filter=blob:none --no-checkout "file://$W/server.git" client

echo "=== without GIT_NO_LAZY_FETCH (current git) ==="
GIT_TRACE="$W/trace.txt" \
    git -C client index-pack --stdin --fix-thin < thin.pack >/dev/null 2>&1 || true
grep -E 'built-in: git (index-pack|fetch)|run_command:.*negotiationAlgorithm' trace.txt
echo "index-pack invocations: $(grep -c 'built-in: git index-pack' trace.txt)"
echo "lazy-fetch spawns:      $(grep -c 'run_command:.*negotiationAlgorithm=noop' trace.txt)"

echo ""
echo "=== with GIT_NO_LAZY_FETCH=1 (what the patch sets) ==="
rm -rf client
git clone -q --no-local --filter=blob:none --no-checkout "file://$W/server.git" client
GIT_NO_LAZY_FETCH=1 GIT_TRACE="$W/trace2.txt" \
    git -C client index-pack --stdin --fix-thin < thin.pack 2>&1 || true
echo "index-pack invocations: $(grep -c 'built-in: git index-pack' trace2.txt)"
echo "lazy-fetch spawns:      $(grep -c 'run_command:.*negotiationAlgorithm=noop' trace2.txt || echo 0)"

--- >8 --- repro-unbounded.sh --- >8 ---

#!/bin/bash
# Unbounded recursion proof. Run repro-depth1.sh first.
# uploadpack.packObjectsHook always returns the same thin pack,
# so every lazy-fetch spawns another. Watchdog kills at depth 50.

set -uo pipefail

W="${TMPDIR:-/tmp}/promisor-recursion-demo"
cd "$W"
test -f thin.pack || { echo "run repro-depth1.sh first"; exit 1; }

cat > evil-pack-objects.sh << EOF
#!/bin/sh
cat > /dev/null
cat "$W/thin.pack"
EOF
chmod +x evil-pack-objects.sh

cat > fake-global.gitconfig << EOF
[uploadpack]
    packObjectsHook = $W/evil-pack-objects.sh
EOF

rm -rf client
GIT_CONFIG_GLOBAL= git clone -q --no-local --filter=blob:none --no-checkout \
    "file://$W/server.git" client

TRACE="$W/unbounded.trace"
rm -f "$TRACE"

echo "=== spawning (watchdog kills at depth 50) ==="
GIT_TRACE="$TRACE" GIT_CONFIG_GLOBAL="$W/fake-global.gitconfig" \
    git -C client index-pack --stdin --fix-thin < thin.pack >/dev/null 2>&1 &
ROOT=$!

LIMIT=50
while kill -0 "$ROOT" 2>/dev/null; do
    N=$(grep -c 'run_command:.*negotiationAlgorithm=noop' "$TRACE" 2>/dev/null || true)
    N=${N:-0}
    if (( N >= LIMIT )); then
        echo ">>> depth $N reached, killing process tree $ROOT <<<"
        pkill -KILL -f "promisor-recursion-demo/client" 2>/dev/null || true
        kill -KILL "$ROOT" 2>/dev/null || true
        sleep 0.2
        pkill -KILL -f "promisor-recursion-demo/client" 2>/dev/null || true
        break
    fi
    sleep 0.02
done
wait "$ROOT" 2>/dev/null
EC=$?

DEPTH=$(grep -c 'run_command:.*negotiationAlgorithm=noop' "$TRACE" 2>/dev/null || true)
DEPTH=${DEPTH:-0}
IPACKS=$(grep -c 'built-in: git index-pack' "$TRACE" 2>/dev/null || true)
IPACKS=${IPACKS:-0}
TMPS=$(ls client/.git/objects/pack/tmp_pack_* 2>/dev/null | wc -l | tr -d ' ')

echo ""
echo "=== without patch (root exit $EC) ==="
echo "recursion depth reached: $DEPTH"
echo "index-pack invocations:  $IPACKS"
echo "tmp_pack_* on disk:      $TMPS"
echo ""
echo "first 4 + last 2 spawns (identical line, no termination condition):"
grep -E 'built-in: git index-pack|run_command:.*negotiationAlgorithm=noop' "$TRACE" | head -4
echo "..."
grep -E 'built-in: git index-pack|run_command:.*negotiationAlgorithm=noop' "$TRACE" | tail -2

echo ""
echo "=== with GIT_NO_LAZY_FETCH=1 (the patch) ==="
rm -rf client; rm -f "$TRACE"
GIT_CONFIG_GLOBAL= git clone -q --no-local --filter=blob:none --no-checkout \
    "file://$W/server.git" client
GIT_NO_LAZY_FETCH=1 GIT_TRACE="$TRACE" GIT_CONFIG_GLOBAL="$W/fake-global.gitconfig" \
    git -C client index-pack --stdin --fix-thin < thin.pack 2>&1 || true
CTRL_DEPTH=$(grep -c 'run_command:.*negotiationAlgorithm=noop' "$TRACE" 2>/dev/null || true)
CTRL_IPACKS=$(grep -c 'built-in: git index-pack' "$TRACE" 2>/dev/null || true)
CTRL_TMPS=$(ls client/.git/objects/pack/tmp_pack_* 2>/dev/null | wc -l | tr -d ' ')
echo "recursion depth:         ${CTRL_DEPTH:-0}"
echo "index-pack invocations:  ${CTRL_IPACKS:-0}"
echo "tmp_pack_* on disk:      $CTRL_TMPS"

rm -rf "$W/client"

Paul