package-diff can generate infinite output

Bug #314436 reported by James Troup on 2009-01-06
14
This bug affects 1 person
Affects Status Importance Assigned to Milestone
Launchpad itself
Critical
Colin Watson
diffutils (Ubuntu)
High
Unassigned

Bug Description

Today, germanium's disk filled up because of this:

-rw-r--r-- 1 lp_queue lp_queue 104G 2009-01-06 16:44 tmpHiK-la/udev_124-12_136~git+34ac42b-1.diff

which is from package-diff. Scott mentioned on IRC:

<Keybuk> the udev tarballs have weirdisms in them
<Keybuk> like looped symlinks and stuff
<Keybuk> but that just spams stderr usually (and upsets dpkg-source)
<Keybuk> it's in the test suite of sysfs weirdisms

Related branches

Celso Providelo (cprov) wrote :

The issue can be reproduced locally with the udev sources from Scott's PPA (https://edge.launchpad.net/~scott/+archive?field.name_filter=udev&field.status_filter=any).

{{{
debdiff udev_136~git+34ac42b-3.dsc udev_136~git+34ac42b-2.dsc
}}}
}}}

Changed in soyuz:
assignee: nobody → cprov
importance: Undecided → High
milestone: none → 2.2.1
status: New → Triaged
Celso Providelo (cprov) on 2009-01-30
Changed in soyuz:
milestone: 2.2.1 → 2.2.2
Changed in soyuz:
milestone: 2.2.2 → pending
James Westby (james-w) wrote :

This appears to be a diff bug.

Thanks,

James

affects: devscripts (Ubuntu) → diffutils (Ubuntu)
Changed in diffutils (Ubuntu):
importance: Undecided → High
assignee: nobody → Scott James Remnant (scott)
status: New → Confirmed
Colin Watson (cjwatson) wrote :

I don't think it's *actually* infinite, as it doesn't appear to be repeating itself directly - but it is producing output that's exponentially large in the number of upward-pointing symlinks.

diff's recursion check right now is merely whether a symlink points to a direct parent. However, an interlocking farm of symlinks of the form ../../sibling or similar defeats this check while permitting pairwise (or worse) recursion that only gets broken once diff encounters a link that resolves to a direct parent.

I've only looked at this relatively briefly, and it's late, but my gut feel is that the best way to fix this would be to check for symlinks pointing up in the directory tree but not pointing to a direct parent, and skip them if they're underneath a directory which we intend to compare recursively anyway. The latter check is slightly hairy, as it interacts oddly with -N or lack thereof and whether the directory is present in the other tree being compared, but I think it would only go wrong in examples even more pathological than this. The only alternative I could think of is to keep a note of all directories we've looked at rather than just the parent chain, and I'm definitely not happy about the unbounded space consumption that would involve.

This is a delicate one, and if we come up with something we should definitely run it by upstream.

Colin Watson (cjwatson) wrote :

Here's a straightforward recipe that shows off the problem. Run this in an empty scratch directory.

  mkdir a b
  for x in `seq 1 8`; do mkdir b/$x; for y in `seq 1 8`; do ln -s ../$(($y + 1)) b/$x/$y; done; done
  diff -Nru a b

Julian Edwards (julian-edwards) wrote :

I will kill Soyuz's diff generation for udev until the diffutils fix makes it back to hardy.

Changed in soyuz:
assignee: Celso Providelo (cprov) → Julian Edwards (julian-edwards)
milestone: pending → 3.0
Changed in soyuz:
status: Triaged → In Progress
Julian Edwards (julian-edwards) wrote :

db-devel/ r8504

Changed in soyuz:
status: In Progress → Fix Committed
Changed in soyuz:
status: Fix Committed → Fix Released
Changed in diffutils (Ubuntu):
assignee: Scott James Remnant (scott) → Colin Watson (cjwatson)
Curtis Hovey (sinzui) on 2009-10-09
tags: added: tech-debt
Colin Watson (cjwatson) on 2012-03-14
Changed in diffutils (Ubuntu):
assignee: Colin Watson (cjwatson) → nobody
Colin Watson (cjwatson) wrote :

Possibly more than just this commit, but this seems to be the main one:

  http://git.savannah.gnu.org/cgit/diffutils.git/commit/?id=e3324651cc1f9f116754a4713e08bfb0bac50150

Changed in diffutils (Ubuntu):
assignee: nobody → Ashish (kulkarniashish88)
assignee: Ashish (kulkarniashish88) → nobody
Colin Watson (cjwatson) wrote :

This happened again today with a different package:

2015-09-17 15:41:12 INFO Running <PackageDiffJob from <SourcePackageRelease cordova-cli (id: 3114039, version: 5.0.0~ubuntu15.04.1-ubuntu2)> to <SourcePackageRelease cordova-cli (id: 3269164, version: 5.3.1-ubuntu2~ubuntu15.04.1~ppa1)>

https://launchpad.net/~cordova-ubuntu/+archive/ubuntu/ppa/+packages

I think we probably need to put some kind of resource limits on this.

Changed in launchpad:
assignee: Julian Edwards (julian-edwards) → nobody
importance: High → Critical
milestone: 3.0 → none
status: Fix Released → Triaged
Ryan Finnie (fo0bar) wrote :

Same result with the 15.04 variant of the package in that PPA:

root 19040 0.0 0.0 41620 1824 ? S 18:52 0:00 \_ CRON
lp_queue 19045 0.0 0.0 4396 608 ? Ss 18:52 0:00 | \_ /bin/sh -c nice -n 10 /srv/launchpad.net/production/launchpad/cronscripts/process-job-source.py IPackageDiffJobSource -q --log-file=DEBUG:/srv/launchpad.net/production-logs/lp_queue/process-job-source.IPackageDiffJobSource.log
lp_queue 19049 0.4 5.6 993456 689984 ? SN 18:52 0:46 | \_ /usr/bin/python -S /srv/launchpad.net/production/launchpad/cronscripts/process-job-source.py IPackageDiffJobSource -q --log-file=DEBUG:/srv/launchpad.net/production-logs/lp_queue/process-job-source.IPackageDiffJobSource.log
lp_queue 32223 64.9 0.0 42240 7100 ? RN 18:59 111:39 | \_ /usr/bin/perl -w /usr/bin/debdiff from/cordova-cli_5.0.0~ubuntu14.04.1-ubuntu2.dsc to/cordova-cli_5.3.1-ubuntu2~ubuntu14.04.1~ppa1.dsc

debdiff 32223 lp_queue 5u REG 8,1 163627839256 4063260 /tmp/debdifftU0kxW.diff
debdiff 32223 lp_queue 6r REG 8,1 163627839256 4063260 /tmp/debdifftU0kxW.diff

Colin Watson (cjwatson) wrote :

This happened again today with cordova-cli, twice. I'm going to arrange to kill debdiff after ten minutes, which should provide fairly reasonable headroom for large packages; 99.9% of successful PackageDiffJobs in 2015 finished inside 09:02, with the maximum being 33:31. I'll make it a configuration option so that we can easily tweak it if need be.

Changed in launchpad:
assignee: nobody → Colin Watson (cjwatson)
status: Triaged → In Progress
Launchpad QA Bot (lpqabot) wrote :
tags: added: qa-needstesting
Changed in launchpad:
status: In Progress → Fix Committed
Colin Watson (cjwatson) on 2015-12-03
tags: added: qa-ok
removed: qa-needstesting
Colin Watson (cjwatson) on 2015-12-03
Changed in launchpad:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Duplicates of this bug

Other bug subscribers