package-diff can generate infinite output

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

This appears to be a diff bug.

Thanks,

James

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.

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

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

I've forwarded this upstream:

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

db-devel/ r8504

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

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.

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

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.

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