package-diff can generate infinite output

[James Troup]

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

[Celso Providelo (cprov)]

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
}}}
}}}

[James Westby (james-w)]

This appears to be a diff bug.

Thanks,

James

[Colin Watson (cjwatson)]

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)]

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)]

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

[Colin Watson (cjwatson)]

I've forwarded this upstream:

  http://lists.gnu.org/archive/html/bug-gnu-utils/2009-09/msg00013.html

[Julian Edwards (julian-edwards)]

db-devel/ r8504

[Colin Watson (cjwatson)]

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

[Colin Watson (cjwatson)]

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.

[Ryan Finnie (fo0bar)]

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)]

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.

[Launchpad QA Bot (lpqabot)]

Fixed in stable r17862 <http://bazaar.launchpad.net/~launchpad-pqm/launchpad/stable/revision/17862>.